Rough implementation of Burrows-Wheeler

bwt.rb

# Rough implementation of BW transform
# As described at the wikipedia page: https://en.wikipedia.org/wiki/Burrows%E2%80%93Wheeler_transform

EOF_CHAR = '|'

def bwt(string)
  string_with_eof = string + EOF_CHAR
  rotations = []
  0.upto(string_with_eof.length - 1) do |i|
    rotations << string_with_eof.chars.rotate(i).join
  end

 rotations.sort.reduce('') do |memo, rotation|
   memo += rotation.chars.last
   memo
 end
end

def inverse_bwt(string)
  rotations = []
  string.length.times { rotations << [] }

  string.length.times do
    rotations.each_with_index do |rotation, index|
      rotations[index].unshift(string[index])
    end

    rotations.sort_by! do |rotation|
      rotation.join
    end
  end

  inverse_array = rotations.select do |rotation|
    rotation.last == EOF_CHAR
  end

  inverse = inverse_array.first.join
  inverse.chomp(EOF_CHAR)
end

string = "^BANANA"

puts inverse_bwt(bwt(string)).inspect