about super permutations
3! number of permutations of 1, 2, 3 = 6 possible
(1 2 3) (1 3 2) (2 1 3) (2 3 1) (3 1 2) (3 2 1)
red color
black color
a "super permutation" is one string that has every permutation in the string
1 2 3 1 2 1 3 2 1 9 entries
1 2 3
2 3 1
3 1 2
2 1 3
1 3 2
3 2 1 optimum
4! number of permutations of 1, 2, 3, 4 = 24 possible
(1 2 3 4 ) (1 2 4 3 ) (1 3 2 4 ) (1 3 4 2 ) (1 4 2 3 ) (1 4 3 2 )
(2 1 3 4 ) (2 1 4 3 ) (2 3 1 4 ) (2 3 4 1 ) (2 4 1 3 ) (2 4 3 1 )
(3 1 2 4 ) (3 1 4 2 ) (3 2 1 4 ) (3 2 4 1 ) (3 4 1 2 ) (3 4 2 1 )
(4 1 2 3 ) (4 1 3 2 ) (4 2 1 3 ) (4 2 3 1 ) (4 3 1 2 ) (4 3 2 1 )
optimum super permutation 33 entries
1 2 3 4 1 2 3 1 4 2 3 1 2 4 3 1 2 1 3 4 2 1 3 2 4 1 3 2 1 4 3 2 1
1 2 3 4
2 3 4 1
3 4 1 2
4 1 2 3
2 3 1 4
3 1 4 2
1 4 2 3
4 2 3 1
3 1 2 4
1 2 4 3
2 4 3 1
4 3 1 2
2 1 3 4
1 3 4 2
3 4 2 1
4 2 1 3
1 3 2 4
3 2 4 1
2 4 1 3
4 1 3 2
3 2 1 4
2 1 4 3
1 4 3 2
4 3 2 1
5! number of permutations of 1, 2, 3, 4, 5 = 124 possible
(1 2 3 4 5) (1 2 3 5 4) (1 2 4 3 5) (1 2 4 5 3) (1 2 5 3 4) (1 2 5 4 3)
(1 3 2 4 5) (1 3 2 5 4) (1 3 4 2 5) (1 3 4 5 2) (1 3 5 2 4) (1 3 5 4 2)
(1 4 2 3 5) (1 4 2 5 3) (1 4 3 2 5) (1 4 3 5 2) (1 4 5 2 3) (1 4 5 3 2)
(1 5 2 3 4) (1 5 2 4 3) (1 5 3 2 4) (1 5 3 4 2) (1 5 4 2 3) (1 5 4 3 2)
...
(5 3 1 2 4) (5 3 1 4 2) (5 3 2 1 4) (5 3 2 4 1) (5 3 4 1 2) (5 3 4 2 1)
(5 4 1 2 3) (5 4 1 3 2) (5 4 2 1 3) (5 4 2 3 1) (5 4 3 1 2) (5 4 3 2 1)
optimum super permutation 153 ? expect ...
1 2 3 4 5 1 2 3 4 1 5 2 3 4 1 ... 1 4 3 2 5 1 4 3 2 1 5 4 3 2 1
1 2 3 4 5
2 3 4 5 1
3 4 5 1 2
4 5 1 2 3
5 1 2 3 4
2 3 4 1 5
3 4 1 5 2
4 1 5 2 3
1 5 2 3 4
5 2 3 4 1
1 4 3 2 5
4 3 2 5
3 2 5 1 4
2 5 1 4 3
5 1 4 3 2
4 3 2 1 5
3 2 1 5 4
2 1 5 4 3
1 5 4 3 2
5 4 3 2 1
6! number of permutations of 1, 2, 3, 4, 5, 6 = 720 possible
(1 2 3 4 5 6) (1 2 3 4 6 5) (1 2 3 5 4 6) (1 2 3 5 6 4) (1 2 3 6 4 5)
(1 2 3 6 5 4) (1 2 4 3 5 6) (1 2 4 3 6 5) (1 2 4 5 3 6) (1 2 4 5 6 3)
(1 2 4 6 3 5) (1 2 4 6 5 3) (1 2 5 3 4 6) (1 2 5 3 6 4) (1 2 5 4 3 6)
...
(6 5 2 3 4 1) (6 5 2 4 1 3) (6 5 2 4 3 1) (6 5 3 1 2 4) (6 5 3 1 4 2)
(6 5 3 2 1 4) (6 5 3 2 4 1) (6 5 3 4 1 2) (6 5 3 4 2 1) (6 5 4 1 2 3)
(6 5 4 1 3 2) (6 5 4 2 1 3) (6 5 4 2 3 1) (6 5 4 3 1 2) (6 5 4 3 2 1)
optimum super permutation 872 expect ...
1 2 3 4 5 6 1 2 3 4 5 1 6 2 3 ... 2 6 1 5 4 3 2 1 6 5 4 3 2 1
1 2 3 4 5 6
2 3 4 5 6 1
3 4 5 6 1 2
4 5 6 1 2 3
5 6 1 2 3 4
6 1 2 3 4 5
3 4 5 1 6 2
4 5 1 6 2 3
...
2 6 1 5 4 3
6 1 5 4 3 2
5 4 3 2 1 6
4 3 2 1 6 5
3 2 1 6 5 4
2 1 6 5 4 3
1 6 5 4 3 2
6 5 4 3 2 1
41! number of permutations of 1, 2, 3, ... ,41 = 87178291200 possible
(1 2 3 4 5 6 7 8 9 10 11 12 13 14) ... (14 13 12 11 10 9 8 7 6 5 4 3 2 1)
optimum super permutation ??? big math question
User your mathmagical thinking to devise an algorithm, that does not
involve searching, to generate super permutations.