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.




Other tasks related to string operations:

Metrics
 Array length
 String length
 Copy a string
 Empty string  (assignment)
Counting
 Word frequency
 Letter frequency
 Jewels and stones
 I before E except after C
 Bioinformatics/base count
 Count occurrences of a substring
 Count how many vowels and consonants occur in a string
Remove/replace
 XXXX redacted
 Conjugate a Latin verb
 Remove vowels from a string
 String interpolation (included)
 Strip block comments
 Strip comments from a string
 Strip a set of characters from a string
 Strip whitespace from a string -- top and tail
 Strip control codes and extended characters from a string
Anagrams/Derangements/shuffling
 Word wheel
 ABC problem
 Sattolo cycle
 Knuth shuffle
 Ordered words
 Superpermutation minimisation
 Textonyms (using a phone text pad)
 Anagrams
 Anagrams/Deranged anagrams
 Permutations/Derangements
Find/Search/Determine
 ABC words
 Odd words
 Word ladder
 Semordnilap
 Word search
 Wordiff  (game)
 String matching
 Tea cup rim text
 Alternade words
 Changeable words
 State name puzzle
 String comparison
 Unique characters
 Unique characters in each string
 Extract file extension
 Levenshtein distance
 Palindrome detection
 Common list elements
 Longest common suffix
 Longest common prefix
 Compare a list of strings 
 Longest common substring
 Find common directory path
 Words from neighbour ones
 Change e letters to i in words
 Non-continuous subsequences
 Longest common subsequence
 Longest palindromic substrings
 Longest increasing subsequence
 Words containing "the" substring
 Sum of the digits of n is substring of n
 Determine if a string is numeric
 Determine if a string is collapsible
 Determine if a string is squeezable
 Determine if a string has all unique characters
 Determine if a string has all the same characters
 Longest substrings without repeating characters
 Find words which contains all the vowels
 Find words which contains most consonants
 Find words which contains more than 3 vowels
 Find words which first and last three letters are equals
 Find words which odd letters are consonants and even letters are vowels or vice_versa
Formatting
 Substring
 Rep-string
 Word wrap
 String case
 Align columns
 Literals/String
 Repeat a string
 Brace expansion
 Brace expansion using ranges
 Reverse a string
 Phrase reversals
 Comma quibbling
 Special characters
 String concatenation
 Substring/Top and tail
 Commatizing numbers
 Reverse words in a string
 Suffixation of decimal numbers
 Long literals, with continuations 
 Numerical and alphabetical suffixes
 Abbreviations, easy
 Abbreviations, simple
 Abbreviations, automatic
Song lyrics/poems/Mad Libs/phrases
 Mad Libs
 Magic 8-ball
 99 Bottles of Beer
 The Name Game (a song)
 The Old lady swallowed a fly
 The Twelve Days of Christmas
Tokenize
 Text between
 Tokenize a string
 Word break problem
 Tokenize a string with escaping
 Split a character string based on change of character
Sequences
 Show ASCII table
 De Bruijn sequences
 Self-referential sequences
 Generate lower case ASCII alphabet




Reference

 The Minimal Superpermutation Problem. by Nathaniel Johnston.
 oeis A180632 gives 0-5 as 0, 1, 3, 9, 33, 153. 6 is thought to be 872.
 Superpermutations - Numberphile. A video
 Superpermutations: the maths problem solved by 4chan - Standupmaths. A video of recent (2018) mathematical progress.
 New Superpermutations Discovered! Standupmaths & Numberphile.


with javascript_semantics
constant nMax = iff(platform()=JS?8:12)
-- Aside: on desktop/Phix, strings can be modified in situ, whereas 
--        JavaScript strings are immutable, and the equivalent code
--        in p2js.js ends up doing excessive splitting and splicing
--        hence nMax has to be significantly smaller in a browser.

atom t0 = time()
string superperm
sequence count
integer pos
 
function factSum(int n)
    integer s = 0, f = 1
    for i=1 to n do
        f *= i
        s += f
    end for
    return s
end function
 
function r(int n)
    if (n == 0) then return false end if
    integer c = superperm[pos-n+1]
    count[n] -= 1
    if count[n]=0 then
        count[n] = n
        if not r(n-1) then return false end if
    end if
    pos += 1
    superperm[pos] = c
    return true
end function
 
procedure superPerm(int n)
    string chars = "123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"[1..n]
    pos = n
    superperm = chars&repeat(' ',factSum(n)-n)
    count = tagset(n)
    while r(n) do end while
    if n=0 then
        if superperm!="" then ?9/0 end if
    elsif n<=7 then
        -- (I estimate it would take at least 5 days to validate 
        --  superPerm(12), feel free to try it on your own time)
        for i=1 to factorial(n) do
            if not match(permute(i,chars),superperm) then ?9/0 end if
        end for
    end if
end procedure 
 
for n=0 to nMax do
    superPerm(n)
    integer l = length(superperm)
    if l>40 then superperm[20..-20] = "..." end if
    string e = elapsed(time()-t0)
    printf(1,"superPerm(%2d) len = %d  %s (%s)\n", {n, l, superperm, e})
end for
