An implementation of the Burrows–Wheeler transform that satisfies https://github.com/zetter/burrows-wheeler-transform

bwt.rb

class BWT
  def encode(string)
    rotations("#{string}$").sort.map{ |s| s.slice(-1, 1) }.join
  end

  def decode(encoded_string)
    encoded_string.chars.inject([]) do |strings|
      encoded_string.chars.zip(strings).map(&:join).sort
    end.detect { |s| s.slice(-1, 1) == '$' }[0..-2]
  end

  private
  def rotations(string)
    (1..string.length).map { |i| string.chars.rotate(i).join }
  end
end