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?

Another answer we can get by hand with math! How neat. Let’s start by just looking at our very first permutation:

0123456789

We know that there are 10! (3,628,800) permutations for this string. 10! is the same as 10 * 9!, which is useful because permutations listed lexicographically change the highest value place last, where n is the number of characters in a string, there are (n-1)! permutations that begin with the same character.

Looking at the example in the question, we can see:

  1. 012
  2. 021
  3. 102
  4. 120
  5. 201
  6. 210

There are 3! total permutations, and \((3-1)! = 2\) permutations that begin with each character. This also means that any n permutation at some point in the list \((3-1)!*n\) is the last possible sequence that begins with the \((n-1)\)th-value character in the string. In other words, it’s just an ordered version of the string that descends after the first character.

To get the very next sequence, the one that begins with the nth-value character and then ascends, we just add 1. This is only because our list begins at 1, as the question assumes. It’s actually easier to start lists at 0 for this, because then you don’t need to worry about adding 1. However, you must then be careful to look for the 999,999th permutation instead of the 1,000,000th. So let’s do that from now on.

Using what we know, we can test some values to find the first character. Our number of characters is 10, so we’re looking at \((10-1)!\)

Our very first permutation in place 0 is 0123456789.

So place \(9!*1 = 362,880\) would have the farthest left character increased by 1, with the rest ascending: 1023456789

Place \(9!*2 = 725,760\) would be: 2013456789

Since \(9!*2 = 1,088,640\) is over our target of 999,999, we know it can’t start with a number higher than 2.

That gives us our first digit! 2

To do this with the remaining digits, we need to know how many times to multiply the size-1 factorial each time. So let’s go through and add them up, remembering that we can’t exceed the target of 999,999, and see if we can reach our number by the end.

The numbers in brackets below represent the cumulative total

\[(9!*2) [725,760]\] \[+ (8!*6) [967,680]\] \[+ (7!*6) [997,920]\] \[+ (6!*2) [999,360]\] \[+ (5!*5) [999,960]\] \[+ (4!*1) [999,984]\] \[+ (3!*2) [999,996]\] \[+ (2!*1) [999,998]\] \[+ (1!*1) [999,999]\]

And we have our sequence. We can figure each successive digit out by counting up in (n-1)!

\(8! * 6\)

  1. 013456789
  2. 103456789
  3. 301456789
  4. 401356789
  5. 501346789
  6. 601345789
  7. 701345689

Second digit = 7

\(7! * 6\)

  1. 01345689
  2. 10345689
  3. 30145689
  4. 40135689
  5. 50134689
  6. 60134589
  7. 80134569

Third = 8

What becomes clear now is that effectively all we’re doing is counting up to the number of times that string needs to be multiplied, skipping over digits we’ve already used.

Let’s employ an easier strategy for the remaining digits.

Our current known digits are 278, the remaining string we’re working with now is 0134569

We need to multiply 6! by 2. Remembering that the strings are zero-indexed, we count up to 0, 1, 3. The fourth digit of our goal string is 3.

Our remaining characters are 014569.

\(5! * 5\) means we count 0, 1, 4, 5, 6, 9 for the fifth digit. (Remaining: 01456)

\(4! * 1\) means 0, 1 for the sixth. (Remaining: 0456)

\(3! * 2\) means 0, 4, 5 for the seventh. (Remaining: 046)

\(2! * 1\) means 0, 4 for the eighth. (Remaining: 06)

\(1! * 1\) means 0, 6 for the ninth. (Remaining: 0)

Since we only have one remaining digit, that has to go next. So our final permutation that falls at place 999,999 for 0-index, or 1,000,000 for 1-index, should be 2783915460.

You could also write out the process of finding the solution as such:

  • 9! * 2 : 0123456789 : [2]

  • 8! * 6 : 013456789 : [27]

  • 7! * 6 : 01345689 : [278]

  • 6! * 2 : 0134569 : [2783]

  • 5! * 5 : 014569 : [27839]

  • 4! * 1 : 01456 : [278391]

  • 3! * 2 : 0456 : [2783915]

  • 2! * 1 : 046 : [27839154]

  • 1! * 1 : 06 : [278391546]

  • 0! * 0 : 0 : [2783915460]

But since I often don’t fully trust myself with solutions like this, I also wrote some code that finds the answer just to make sure it matches by essentially brute force checking all the permutations up to 1 million.

The algorithm I’m using is explained in this Wikipedia article.

seq = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

count = 1         #index begins at 1
limit = 1000000   #for 0 index, limit = 999999

while count < limit and seq != sorted(seq, reverse=True):
    for k in range(len(seq)-2, -1, -1):
        if seq[k] < seq[k+1]:
            
            for l in range(len(seq)-1, k-1, -1):
                if seq[k] < seq[l]:
                    swap  = seq[k]
                    seq[k] = seq[l]
                    seq[l] = swap
                    seq[k+1:] = seq[len(seq)-1:k:-1]
                    break      
            break
    count += 1
    
print(seq)
Click to reveal output 
[2, 7, 8, 3, 9, 1, 5, 4, 6, 0]

See problem 24 on projecteuler.net