How to resolve the algorithm Superpermutation minimisation step by step in the J programming language
How to resolve the algorithm Superpermutation minimisation step by step in the J programming language
Table of Contents
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:
Step by Step solution about How to resolve the algorithm Superpermutation minimisation step by step in the J programming language
Source code in the j programming language
approxmin=:3 :0
seqs=. y{~(A.&i.~ !)#y
r=.{.seqs
seqs=.}.seqs
while.#seqs do.
for_n. i.-#y do.
tail=. (-n){. r
b=. tail -:"1 n{."1 seqs
if. 1 e.b do.
j=. b i.1
r=. r, n}.j{seqs
seqs=. (<<<j) { seqs
break.
end.
end.
end.
r
)
(#, #@approxmin)@> (1+i.8) {.&.> <'abcdefghijk'
1 1
2 3
3 9
4 33
5 153
6 873
7 5913
8 46233
You may also check:How to resolve the algorithm Dynamic variable names step by step in the Mathematica / Wolfram Language programming language
You may also check:How to resolve the algorithm Fractran step by step in the Mathematica / Wolfram Language programming language
You may also check:How to resolve the algorithm 100 doors step by step in the Janet programming language
You may also check:How to resolve the algorithm AVL tree step by step in the Component Pascal programming language
You may also check:How to resolve the algorithm Increment a numerical string step by step in the LabVIEW programming language