Superpermutation in Ruby

superpermutation

# Naive implementation for finding the superpermutation of n symbols
# https://en.wikipedia.org/wiki/Superpermutation

n = 4
permutations = (1..n).to_a.permutation.map{|a| a.join}

s = permutations.first
permutations.shift
while (permutations.length > 0)
  idx = nil
  nn = n
  while (idx.nil? && nn > 1)
    nn -= 1
    # Find the longest match for n - 1, n - 2 and so on
    idx = permutations.index {|c| c[0..nn - 1] == s[-nn..-1]}
  end
  # Add the difference between the strings
  s << permutations[idx][nn..n - 1]
  permutations.delete_at(idx)
end

if n == 3 && s == "123121321"
  puts "Correct for n = 3"
end
if n == 4 && s == "123412314231243121342132413214321"
  puts "Correct for n = 4"
end

puts s
puts "Length #{s.length}"