Verifying a superpermutation for 6 symbols

check_super_permutation_6.rb

# See the Aug. 2014 paper Tackling the Minimal Superpermutation Problem by Robin Houston at http://arxiv.org/abs/1408.5108
# It announces a superpermutation for 6 symbols with length 872
# This Ruby script verifies it is a superpermutation and finds that all permutations only occur once.
# Kind of complements http://arxiv.org/src/1408.5108v1/anc/splitsuperperm.py ("Take a superpermutation, and print it as a sequence of permutations.")
# Invocation:
# ruby check_super_permutation_6.rb
# (Runs in 0.05 secs on a standard laptop, no optimizations necessary)

# Could also read this from http://arxiv.org/src/1408.5108v1/anc/superperm-6-866.txt
SUPER_PERMUTATION =<<END_PERM.gsub("\n",'')
1234561234516234512634512364513264513624513642513645213645123465123415
6234152634152364152346152341652341256341253641253461253416253412653412
3564123546123541623541263541236541326543126453162435162431562431652431
6254316245316425314625314265314256314253614253164523146523145623145263
1452361452316453216453126435126431526431256432156423154623154263154236
1542316542315642135642153624153621453621543621534621354621345621346521
3462513462153642156342165342163542163452163425163421564325164325614325
6413256431265432165432615342613542613452613425613426513426153246513246
5312463512463152463125463215463251463254163254613254631245632145632415
6324516324561324563124653214653241653246153264153261453261543265143625
1436521435621435261435216435214635214365124361524361254361245361243561
2436514235614235164235146235142635142365143265413625413652413562413526
41352461352416352413654213654123
END_PERM

abort "String length #{SUPER_PERMUTATION.length} is not 872" unless SUPER_PERMUTATION.length == 872
abort "String has characters other than 0,..,6" unless SUPER_PERMUTATION =~ /\A[1-6]+\Z/

@match_counts = {}
ONE_TO_SIX = (1..6).map { |x| x.to_s }

def check_permutation(permutation)
  abort "#{permutation.inspect} is not a permutation" unless permutation.size == 6
  abort "#{permutation.inspect} is not a permutation" unless permutation.split('').sort == ONE_TO_SIX
  match_count = SUPER_PERMUTATION.scan(/#{permutation}/).size
  abort "No match for #{permutation.inspect}" if match_count < 1
  abort "Already added count for permutation #{permutation.inspect}" if @match_counts.has_key?(permutation)
  @match_counts[permutation] = match_count
end

ONE_TO_SIX.permutation do |permutation|
  check_permutation permutation.join('')
end

all_have_one_match = true
@match_counts.sort_by { |k,v| v}.each do |k_v|
  k,v = k_v
  if v != 1
    all_have_one_match = false 
    puts "For permutation #{k_v[0]} have #{k_v[1]} matches"
  end
end

puts "All #{@match_counts.length} permutations have one match only." if all_have_one_match
puts "Some of the #{@match_counts.length} permutations have more than one match." unless all_have_one_match

Sampel run.

$ ruby check_super_permutation_6.rb
All 720 permutations have one match only.