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?
I decided to do this in Excel. The methodology I used was the following. Whatever digit we pick for the 1st place, the remaining 9 digits will provide 9! or 9x8x7x6x5x4x3x2x1 = 362,880 permutations. If we divide 1,000,000 by this, we get 2.something. In lexicographic order all permutations starting with 0 and 1 will account for 725,760 permutations. So, the first digit in our solution will be 2. We are now looking for the 1,000,000 - 725,760 or 274,240th permutation in the 2xxxxxxxxx group. Repeat the analysis for each of the next digits to get to the answer. Keep two things in mind. The digit to pick is the CEILING({target remaining}/{number of permutations for next n digits}) and if we have an exact division, the remainder for the next calculation should remain unchanged.
In some cell (I picked G10) enter the target string '0123456789 (the leading apostrophe ensures Excel treats the data as text and not a number.
In some column, in 10 contiguous cells (I picked A11:A20), enter the numbers. These represent the number of digits available for the remaining positions.
| 9 |
| 8 |
| 7 |
| 6 |
| 5 |
| 4 |
| 3 |
| 2 |
| 1 |
| 0 |
Then, in B11 enter the formula =FACT(A11).
C11 contains the target (1000000) and you can use other numbers to test the method. Use =FACT(10) for the last lexicographic permutation.
In D11 enter =INT(C11/B11)
In E11 enter =B11*D11
In F11 enter =MID(G10,MIN(LEN(G10),CEILING(C11/B11,1)),1) This formula extracts the element of interest from the string.
In G11 enter =SUBSTITUTE(G10,F11,"") This represents the remaining string.
In C12 enter the formula =IF(E11=C11,C11,C11-E11)
Copy B11,D11:G11 down to 12. Copy B12:G12 down to 13:20. Read off the answer in column F.
