Arsène Lupine’s secret: superpermutations
How to represent all the possible permutations of a set by a short sequence? This settling game is not only of interest to mathematicians — it can also help stunners, burglars and traveling salesmen.
Some simple problems fascinate mathematics enthusiasts and lead them to the heights of research. The problem we are going to talk about in this topic is in this category. Stranger and rarer, a breakthrough in research on superpermutations comes from a contributor who wished to remain anonymous! In addition, the mathematics of superpermutations can be of interest to burglars and stunners who have forgotten their passcode.
The permutations of a set are the different ways of classifying its elements. There are for example 6 possible permutations of a set of three elements {1, 2, 3} which are: 123, 132, 213, 231, 312 and 321.
In the case of a set having n elements, there are n! = N (n — 1) … 3.2.1 possible permutations. The number n! (“Factorial n”) grows very quickly with n:
1! = 1; 2! = 2; 3! = 6; 4! = 24; 5! = 120;
6! = 720; 7! = 5,040; 8! = 40,320; 9! = 362,880; 10! = 3,628,800; 11! = 39,916,800; 12! = 479,001,600; 13! = 6,227,020,800; 14! = 87,178,291,200; etc.
2. Permutations and factorials
The various ways of arranging a set of n elements, or permutations of this set, are n! = 1 × 2 × 3 × … × n (factorial n): we choose the element to put at the head (n possibilities); we choose the element to be placed in second (n — 1 possibilities); etc. The sequence of factorials grows very quickly:
0! = 1
1! = 1
2! = 2
3! = 6
4! = 24
5! = 120
6! = 720
7! = 5,040
8! = 40,320
9! = 362,880
10! = 3,628,800
11! = 39,916,800
12! = 479,001,600
13! = 6 227 020 800
14! = 87 178 291 200
15! = 1,307,674,368,000
16! = 20,922,789,888,000
17! = 355,687,428,096,000
18! = 6,402,373,705,728,000There are thus 4! = 24 permutations of 4 elements, and therefore 24! ways to tidy up
these permutations.
The problem of superpermutations for n consists in proposing a sequence of integers between 1 and n, as short as possible, in which we find each permutation of {1, 2, …, n} as a sequence of elements side by side.
For n = 2, the sequence 121 of length 3 is a superpermutation, because there are 12 and 21 which are the only two permutations of {1, 2}. By swapping the role of 1 and 2, we obtain a second superpermutation of length 3: 212. This possibility of obtaining other superpermutations of the same length as soon as we have one works of course for all n, and each superpermutation found for n will give n! the same length, since there is n! ways of permuting the symbols of {1, 2,…, n}.
First superpermutations
For n = 3, the sequence 123121321 is a superpermutation; we find there the 6 permutations 123, 132, 213, 231, 312, 321, in the order 123, 231, 312, 213, 132, 321.
To build it, we took the 6 permutations and put them one behind the other, choosing an order allowing them to be merged as well as possible. Behind 123, we chose to put 231, which, by merging them, gives 1231 and therefore saves 2 symbols compared to a juxtaposition without fusion.
The superpermutation proposed for n = 3 has length 9. Is it possible to have it shorter? The answer is no. To be convinced of this, you have to do a little reasoning .
1. Superpermutations and safe opening
A superpermutation of order n = 3 is a sequence of numbers taken from 1, 2 and 3 where we find all the permutations of the three numbers 1, 2, 3, that is to say 123, 132, 213, 231, 312, 321. Of course, by putting the permutations one behind the other, we have what we are looking for with a sequence of length 18: 123132213231312321. However, we can do better: the sequence 123121321 is suitable. The length 9 is therefore possible for n = 3.
Let us show that we cannot do better than 9. Suppose that a sequence n1n2n3n4n5n6n7n8 of 8 numbers is suitable for n = 3, that is to say that the 6 sequences n1n2n3, n2n3n4, n3n4n5, n4n5n6, n5n6n7, n6n7n8 are the 6 permutations of {1, 2, 3}, which means, in particular, that they are all different.
For n1n2n3 to be a permutation, n1 must be different from n2 and different from n3. For n2n3n4 to be a permutation, n4 must be different from n2 and n3. So necessarily n1 = n4.
Likewise, by considering n2n3n4 and n3n4n5, we conclude that n2 = n5; and considering n3n4n5 and n4n5n6, we deduce that n3 = n6. Therefore, we would have n1n2n3 = n4n5n6, which is in contradiction with the assumption that the 6 sequences n1n2n3, n2n3n4, n3n4n5, n4n5n6, n5n6n7 and n6n7n8 are all different. Conclusion: there is no superpermutation of length 8 for n = 3.
For n = 4, we find 123412314231243121342132413214321, of length 33, which we also show (it’s a little more complicated, of course!) To be the shortest possible superpermutation for n = 4.
One possible application of superpermutations is opening a closed safe whose combination has been lost. To open it, you have to position the boot slider by making it occupy 4 successive different positions which constitute the opening code, for example 6 then 2 then 1 then 4. We have forgotten the 4 digits of the opening code. We could try all the combinations one after the other by moving the cursor 4 times for each one. We have 10 × 9 × 8 × 7 / (4 × 3 × 2) = 210 subsets of 4 digits, and for each of these subsets, there are 4! = 24 possible orders. In total, we therefore have 210 × 24 × 4 = 20,160 cursor movements to be made by the natural enumeration method.
By using the superpermutation of {1, 2, 3, 4} of length 33, however, a lot of movement can be saved. For each set of 4 digits {a, b, c, d}, we copy the superpermutation of {1, 2, 3, 4} by replacing 1 by a, 2 by b, 3 by c, 4 by d, and we use the superpermutation of {a, b, c, d} to try all the combinations. We will thus make 33 movements instead of 4 × 24 = 96. In total, we will only make (at most) 33 × 210 = 6 930 cursor movements instead of 20 160, which corresponds to a gain of more than 65 %. By paying attention to the order in which you consider the 4-digit subsets, you can save a few more moves.
For n greater than 3, we can proceed by trial and error or by using programs which explore all the possible cases. We will see that we quickly encounter the limits of the computing capacity of our computers, because the exponential growth of n! is really very fast. However, there are general arguments giving information on the superpermutations sought which simplify the treatment of particular cases.
Here are some of those results on the length of superpermutations. They have been found by both mathematical researchers and enthusiasts passionate about the problem — especially Greg Egan, Australian sci-fi author, who is responsible for the novel Permutation City and who maintains an excellent site. internet on the subject.
5. Greg Egan
Greg Egan, born in 1961, is a Canadian science fiction author and programmer who is interested in the problem of superpermutations. He offers a website on the problem.
He published a successful novel translated into French: Permutation City or La Cité des permutants, which deals with multiple worlds and which, despite its title, does not deal with superpermutations!
Find, for a given n, the one that is the shortest
The shortest superpermutation for n has at least n! + N — 1 symbols. Indeed, each symbol of a superpermutation can only be the beginning of one permutation at most: therefore at least n is required! symbols in a superpermutation. However, the last n — 1 symbols cannot be the start of a permutation, because there are not enough following symbols: a superpermutation for n therefore has at least n! + N — 1 symbols.
A more detailed reasoning proposed in 1993 by the mathematicians Daniel Ashlock and Jenett Tillotson shows that the minimum length is at best n! + (N — 1)! + (N — 2). Another reasoning, more recent and more efficient, gives the lower bound: n! + (N — 1)! + (N — 2)! + (N — 3).
This result is the best known today for the reduction in the length of a superpermutation. He has a bit of a strange story.
In 2011, on the 4chan internet forum, Internet users discussed the problem of knowing how to go about broadcasting as quickly as possible the episodes of a television series which contains n, so that we can see them in all possible orders depending on when you start watching the broadcast of the series. The problem is exactly that of finding the shortest superpermutation of n elements.
An anonymous internet user claimed that it was impossible to succeed in less than n! + (N — 1)! + (N — 2)! + (N — 3) episode broadcasts. He gave imperfect arguments, but relatively precise all the same.
A few years later, in 2018, a group of mathematicians consisting of Robin Houston, Jay Pantone, and Vince Vatter, concerned about the problem of superpermutations, took the anonymous contributor’s ideas, wrote them down accurately and comprehensively, and put them together. published. Quite honestly, the group of mathematicians published the result (https://oeis.org/A180632/a180632.pdf) under their three names preceded by a fictitious name, Anonymous 4chan Poster, to the awesome and still unknown hobbyist.
Knowing a lower bound does not guarantee that you will find a superpermutation of the indicated length; it’s just the claim that it’s impossible to make it shorter. After looking for the upper bounds of the size of the best superpermutation, it is natural to look at upper bounds, this time trying to find the smallest possible ones. If we succeed in bringing together the lower bound and upper bound, the problem will be solved: we will know what is the length of the shortest superpermutations for all n.
What is the maximum length of a superpermutation?
First of all, it is obvious that for any integer n, there exists a superpermutation of length n × n !, since by putting one after the other without any merging the n! permutations which each have n symbols, we obtain a superpermutation of length n × n!.
The superpermutation of length n × n! is not really smart, because it does not exploit any possibility of merger. We must try to do better. This is what the very nice result offers: “For every positive integer n, there exists a superpermutation of length n! + (N — 1)! + … + 2! + 1. “
The gain with respect to n × n! is more important than n is large. A small calculation indeed shows that for n = 3 the gain is 9, for n = 4 the gain is 63, for n = 5 the gain is 447, for n = 6 the gain is 3447, for n = 7 the gain is 35,280, for n = 8 the gain is 322,560.
The demonstration that n! + (N — 1)! + … + 2! + 1 symbols are always sufficient for a superpermutation of {1, 2,…, n} results from a construction which allows many mergers, and from a magnificent reasoning proposed in 2013 by Nathaniel Johnston, from Mount Allison University, at Sackville, Canada. The construction exploits the idea that from one superpermutation for n to the next for n + 1, we can reuse the mergers that we have been able to make and therefore that the new mergers that we introduce at each step and the successful mergers at the previous step are cumulative and allow increasingly significant savings in number of symbols
3. Superpermutation of length n! + (n — 1)! + … + 2! +1
For every positive integer n, there exists a superpermutation whose length is: n! + (N — 1)! + … + 2! + 1.
Let’s see the superb demonstration of this result proposed in 2013 by Nathaniel Johnston.
For n = 3, we have a superpermutation of length 9, and we have 9 = 3! + 2! + 1. Similarly, for n = 4, we have a superpermutation of length 33 = 4! + 3! + 2! +1. The result is therefore true for n = 3 and n = 4.
Let us reason by induction: we suppose the result to be true for n and we try to prove that it is then true for n + 1. To follow the reasoning, we will detail the steps to go from a superpermutation corresponding to n = 3 to a superpermutation corresponding to n = 4, but the method is general and allows to pass from a superpermutation of length n! + (N — 1)! + … + 2! + 1, for n, to a superpermutation of length (n + 1)! + N! + (N — 1)! + … + 2! + 1, for n + 1.
So let’s take a superpermutation for n = 3 of length 1 + 2! + 3! : 123121321. Let us show all the permutations of {1, 2, 3} in the order in which they appear: 123, 231, 312, 213, 132, 321 (we did not show 121, because it is not is not a permutation).
We join these permutations by merging what can be: for example, we join 123 and 231 which gives 1231, because we exploit that 123 ends with 23 and that 231 starts with 23. After all the mergers, we obtain a sequence 123121321 length 9 = 3! + 2! +1! as expected.
Now, starting from the list of permutations 123, 231, 312, 213, 132, 321, we build a new one by doubling each permutation and placing a 4 between the identical permutations:
123 4 123, 231 4 231, 312 4 312,
213 4 213, 132 4 132, 321 4 321.
Let us now merge the terms of this sequence as much as possible. For n = 4, we get 123412314231243121342132413214321. What we earn from mergers is equal to what we earn (9 digits) by merging 123, 231, 312, 213, 132, 321 to get 123121321. By induction hypothesis, in the general case, that saves n × n! — (1 + 2! + … + n!) Symbols.
In the general case (and for n + 1), the sequence that we obtain by these mergers has the length:
2n × n! + n! — [n × n! — (1 + 2! + … + n!)].
The first term, 2n × n !, comes from the fact that we have copied the n twice! permutations, which are each of length n; the second term comes from the copy n times the value n + 1 (the 4 in our example); and the term subtracted comes from what you earn from mergers. The resulting expression is simplified: 2n × n! + n! — [n × n! — (1 + 2! + … + n!)] = N × n! + n! + (1 + 2! + … + n!) = N! (n + 1) + (1 + 2! + … + n!) = 1 + 2! + … + n! + (n + 1)!. The sequence of numbers of our construction therefore has a length of 1 + 2! + … + n! + (n + 1)!.
Let us now show that it does indeed contain all the permutations of {1, 2, …, n + 1}. Any permutation P of {1, 2, …, n + 1} is of the form A (n + 1) B where A and B are sequences using in total n numbers all different taken from {1, 2,. .., n} and therefore such that AB is a permutation of {1, 2, …, n}. This means that P is somewhere in what we have built, because somewhere we have the sequence AB (n + 1) AB. CQFD.
To recap, denote by S (n) the length of the shortest superpermutation for n. For n = 1, 2, 3, the problem is solved: S (1) = 1 (obvious); S (2) = 3 (obvious); S (3) = 9 (explained above and in Box 1).
Taking into account the best lower bound and the best upper bound known, we know that for all n ≥ 4, we have:
n! + (n — 1)! + (n — 2)! + (n — 3) ≤ S (n) ≤ n! + (N — 1)! + … + 2! + 1.
For n = 4, this means: 24 + 6 + 2 + 1 = 33 ≤ S (4) ≤ 24 + 6 + 2 + 1 = 33. The superpermutation obtained by the method described in box 2 is: 123412314231243121342132413214321. Sa length is 33, so this is the best possible result.
A calculation by program gives more precise information. It lets you know that the only other possible superpermutations are the 4! = 24 which can be deduced from the one given above by permutation of the symbols and that there are no others. As an example, let’s give one of the superpermutations obtained by permuting the symbols of the given superpermutation. If we change 1 to 2, 2 to 3, 3 to 4 and 4 to 1, we get the superpermutation: 234123421342314232413243124321432.
For nearly twenty years, the natural assumption that the formula n! + (N — 1)! + … + 2! + 1 gave the minimum length of a superpermutation for n was allowed, until the study of cases n = 5 and n = 6 changes the situation.
For n = 5, the method in Box 3 provides a superpermutation of length 5! + 4! + 3! + 2! +1! = 153. Making a fairly effective program which, for n = 5, tries to find something better without forgetting anything, or shows that you cannot do better than 153, is not easy. However, in March 2014, Ben Chaffin succeeded, and his astute exploration program uncovered 8 superpermutations of length 153, none of which are interchangeable by changing the names of the symbols. Each of the 8 superpermutations gives 120 = 5! superpermutations by changes in the names of symbols. The program also shows that 153 is impossible to improve. Here is one of the eight superpermutations found: 123451234152341253412354123145231425314235142315423124531243512431524312543121345213
(see here).
This result establishes that the lower bound discovered thanks to the anonymous Internet user is not precise enough: for n = 5, there are no superpermutations corresponding to the announced lower bound. But this result also shows that the method in Box 3 does not give all that is possible, and suggests that it is possible to improve the upper bound n! + (N — 1)! + … + 2! + 1.
What happens for n = 6 effectively proves that the known upper bound is not precise enough either. The formula n! + (N — 1)! + … + 2! +1 ceases to be valid for S (6). Robin Houston realized this when he understood that the algorithms for solving the traveling salesperson problem (see Box 4) adapt to the problem, and that, thanks to those developed by researchers in applied mathematics, we shows that there exists a superpermutation of {1, 2, 3, 4, 5, 6} which, instead of having the length 6! + 5! + 4! + 3! + 2! + 1 = 873, has only 872 symbols. The result is catastrophic for the known theoretical upper bound, because from this superpermutation for n = 6, we can, using the method in Box 3, find some that beat n! + (N — 1)! + … + 2! + 1 for any n greater than 6.
4.the traveling salesman problem
A number of cities are given, and the network of roads connecting the cities is known. When there is a road between two cities, we know the length of the road that connects them. The traveling salesman’s problem is to come up with a tour plan to visit all the cities, just once each, making the shortest possible route.
Whether, for a given length L, there is a solution giving a travel plan of less than L kilometers is a problem of the NP-complete category. This means that we do not know how to solve it quickly (in polynomial time), and that if we knew it, we could quickly solve (in polynomial time) all the problems of a large class of problems (the NP class), this which seems improbable. Put more simply: we do not know how to quickly solve the general problem of the traveling salesman and it is unlikely that we will ever know it; you have to be content with slow methods, or methods that do not guarantee the best possible result.
There are such methods as well as programs which give fairly good results, although not the best possible. For example, Julien Coupey, who worked on mobility at the Femto-ST Institute in Besançon and who now works for the start-up Verso, is developing a program that deals with tours of a fairly large number of cities. Thus, for a problem concerning 93 French cities, its program proposes the solution shown above.
Solving the problem of superpermutations comes down to a traveling salesman problem. Let’s explain the idea on an example by taking n = 3.
The permutations of {1, 2, 3} are 123, 132, 213, 231, 312, 321. A superpermutation is like a path connecting these permutations. Between two permutations, the distance between them can be 1, 2 or 3:
- between 123 and 231, the distance is 1, because by correctly merging 123 and 231, which gives 1231, we only extend 123 by one symbol;
- between 123 and 312, the distance is 2, because by merging the two permutations, we obtain 12312, which lengthens 123 by two symbols;
- between 123 and 132, the distance is 3, because no merger is possible and so if we want the two permutations one after the other, we have to take 123132, which lengthens 123 by three symbols.
This way of looking at permutations and their mutual distances defines the equivalent of a map with distances. The problem of finding a superpermutation then becomes that of finding the shortest route plan for the traveling salesperson who wants to visit all the permutations on this map.
The drawing below by Greg Egan represents the traveling salesman’s map for n = 3: the “roads” of length 1 between permutations are drawn in red, that of length 2 (between 312 and 213) is drawn in blue. The other “roads” are not drawn. The shortest possible superpermutation, 123121321, of length 9, is represented by the succession of five routes: two in red, one in blue, two in red.
The traveling salesman problem is an important problem in applied mathematics because many problems are related to it. Methods and programs to solve it have been developed and perfected. These methods were used to solve the problem of superpermutations and led to a series of records (see main text).
A theoretical advance confirms what the computer calculation has shown. Using an idea from 2013 by Canadian mathematician Aaron William, science fiction writer Greg Egan has indeed proposed a construction of the same type as that shown in Box 3, which this time indicates that we can for all n ≥ 6 have a superpermutation whose length will not exceed n! + (N — 1)! + (N — 2)! + (N — 3)! + (N — 3).
The theoretical framework of S (n) has become better: n! + (N — 1)! + (N — 2)! + (N — 3) ≤ S (n) ≤ n! + (N — 1)! + (N — 2)! + (N — 3)! + (N — 3).
The right side and the left side appear close. This is an illusion, because the gap between the two is (n — 3) !, a quantity which increases very quickly when n increases.
Aaron William and Greg Egan’s general method for n = 7 gives a superpermutation of length 5,908, which saves 5 symbols compared to 5,913 = 7! + 6! + 5! + 4! + 3! + 2! + 1. For n = 8, the method gives a length of 46 205, ie a gain of 28 compared to 46 233 = 8! + 7! + … + 2! + 1. For n = 9, the method gives a length of 408 966, that is 147 less than 409 113 = 9! + 8! + … + 2! + 1.
The new method is certainly very good, but it is not the ultimate method. Indeed, for n = 7, a program of Bogdan Coanda found a superpermutation of length 5,907, better than the 5,908 of the method of Aaron William and Greg Egan, record again broken by a superpermutation of length 5,906 found recently. by a program this time from Robin Houston.
Today, some think that we are close to a definitive solution for all n, but nothing is won, and for the moment we are only certain about S (n) for S (1) = 1, S (2) = 3, S (3) = 9, S (4) = 33 and S (5) = 153.
Some related problems
Other problems arise similar to that of superpermutations.
De Bruijn’s sequences, to which we have devoted a section (“A mathematical card trick”, Pour la Science, n ° 441, July 2014), consists in looking for a sequence which contains not all the permutations, but all the sequences. of a fixed length k using n symbols. For example, the De Bruijn sequence 00000100101100111110001101110101 contains the 32 possible sequences of length 5, made up of 0 and 1. We therefore find 00000, 00001, 00010, 00011,…. In De Bruijn’s problem, we consider that the continuation is closed in on itself and therefore that once arrived at the end, we start again at the beginning. This is important because the sequence 10100 is only obtained by taking the last three symbols and the first two.
The problem of the length of De Bruijn sequences is simpler than that of superpermutations, since we can, for example, show that there exist De Bruijn sequences of length 2k for all k in the case of the problem of sequences of 0 and of 1 of length k, and that this result is the best possible.
A problem still quite close to that of superpermutations is studied by mathematicians by considering the notion of extracted sequence. If we take the sequence 1232132, we find 123, 132, 213, 231, 312, 321, but this time it is only true by agreeing to take the symbols sought even if they are not side by side ( we speak of “extracted suite”). For example, 231 is obtained by taking the red symbols in 1232132 and 312 is obtained by taking the red symbols in 1232132.
We have shown that the smallest integer equal to or exceeding n²–7n / 3 + 19/3 is always a sufficient length to succeed in having a sequence extracted for each permutation of {1, 2,…, n}. This number is however a simple upper bound and, as in the case of superpermutations, it is not known exactly what is, with certainty, the smallest sufficient length for n.
Data packing problems are trickier than you might expect!
