superpermutation.rb

class SuperPermutation
  CHARS = ('a'..'z').map(&:to_sym)

  def initialize(size)
    @size  = size
    @chars = CHARS.take(@size)
    @used  = {}
    @index = Hash.new { |h, k| h[k] = [] }

    @chars.permutation.each do |seq|
      @used[seq] = false
      (0...@size).each { |n| @index[seq.take(n)] << seq }
    end
  end

  def generate
    @string = @chars.clone
    @count  = @used.size - 1
    @cursor = 0

    @used[@string] = true

    build_string until @count == 0

    @string
  end

  def build_string
    @cursor += 1
    prefix = @string.drop(@cursor)

    picked = @index[prefix].find { |seq| not @used[seq] }
    return unless picked

    @string.concat(picked.drop(prefix.size))

    @used[picked] = true
    @count -= 1
  end
end


(1..6).each do |n|
  sp  = SuperPermutation.new(n)
  seq = sp.generate

  p [seq.size, seq]
end