Skip to content

Instantly share code, notes, and snippets.

@jonelf
Created March 13, 2024 17:17
Show Gist options
  • Save jonelf/754e96cbf1119270c464e6a48717d06c to your computer and use it in GitHub Desktop.
Save jonelf/754e96cbf1119270c464e6a48717d06c to your computer and use it in GitHub Desktop.
Superpermutation in Ruby
# 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}"
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment