In this article we want to briefly discuss a possible solution to the project euler problem 24 which asks:
A permutation is an ordered arrangement of objects. For example, 3124 is one possible permutation of the digits 1, 2, 3 and 4. If all of the permutations are listed numerically or alphabetically, we call it lexicographic order. The lexicographic permutations of 0, 1 and 2 are:
012 021 102 120 201 210
What is the millionth lexicographic permutation of the digits 0, 1, 2, 3, 4, 5, 6, 7, 8 and 9?
One possible approach could obviously be to brute force all the lexicographical permutations and then take the millionth element out of the previously sorted collection of permutation (interpreted as number). The drawback of this solution is that unfortunately the number of permutations is more than exponential, is .
We want to show here a more mathematical/combinatorial approach. First of all start considering that how the permutations looks like.
First permutations are (thanks to Stefano Germano for typo correction) .
A deeper look at the permutations reveals that are all the sequences starting with 0 and concatenated with a permutation of the ramaining 9 elements . How many of them? .
It means that the permutation we are looking for has to be greater than the th permutation: .
From this we can deduce that we can also skip all the sequences starting by 1 because they produces (again) permutations and
. Moreover our millioth permutation is in the sequences starting with 2 because (hence is not in the permutations starting with 3).
Infact:(the following shows the starting and ending sequence of permutations starting with a particular number and their indices in the ordered sequence of all permutations)
Our permutation is in the set , set of all the permutation starting with 2.
We can repeat again the process on the remaining substring of length 9. This time is we fix the 2-th position (with an element taken from ) we have 8! permutations. In particular , hence our permutation is in the interval:
We can repear the process again and again until the interval is small enough.
We can speed up the process noticing that
and selecting at each step from the set of non fixed elements the th element.
The following describe the process (on the right the number of permutation at each step).
- # 1
At this point we have restricted all the interval to only four permutations (we have skipped the first 999996). We can list all the permutation of [0,4,6] to found the 4-th and append it to the prefix of our permutation.
- [4,6,0], Here we go!
Our solution is now: 2,7,8,3,9,1,5,0,4,6.