Problem Statement

A superpermutation of N different characters is a string consisting of an arrangement of multiple copies of those N different characters in which every permutation of those characters can be found as a substring. For example, representing the characters as A..Z, using N=2 we choose to use the first two characters 'AB'. The permutations of 'AB' are the two, (i.e. two-factorial), strings: 'AB' and 'BA'. A too obvious method of generating a superpermutation is to just join all the permutations together forming 'ABBA'. A little thought will produce the shorter (in fact the shortest) superpermutation of 'ABA' - it contains 'AB' at the beginning and contains 'BA' from the middle to the end. The "too obvious" method of creation generates a string of length N!*N. Using this as a yardstick, the task is to investigate other methods of generating superpermutations of N from 1-to-7 characters, that never generate larger superpermutations. Show descriptions and comparisons of algorithms used here, and select the "Best" algorithm as being the one generating shorter superpermutations. The problem of generating the shortest superpermutation for each N might be NP complete, although the minimal strings for small values of N have been found by brute -force searches.

Let's start with the solution:

-V MAX = 12

[Char] sp
V count = [0] * MAX
V pos = 0

F factSum(n)
   V s = 0
   V x = 0
   V f = 1
   L x < n
      f *= ++x
      s += f
   R s

F r(n)
   I n == 0
      R 0B
   V c = :sp[:pos - n]
   I --:count[n] == 0
      :count[n] = n
      I !r(n - 1)
         R 0B
   :sp[:pos++] = c
   R 1B

F superPerm(n)
   :pos = n
   V len = factSum(n)
   I len > 0
      :sp = [Char("\0")] * len
   L(i) 0 .. n
      :count[i] = i
   L(i) 1 .. n
      :sp[i - 1] = Char(code' ‘0’.code + i)
   L r(n) {}

L(n) 0 .< MAX
   superPerm(n)
   print(‘superPerm(#2) len = #.’.format(n, sp.len))