Problem 24:Lexicographic permutations

*Difficulty: Easy

Problem:

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?

How to solve:

  1. Brute force, generate all lexicographic permutations, stop when the number is the 1000000th lexicographic permutation
  2. Analyze

Here is the second way, I don’t write code for this problem, because I feel tired, and because I think it’s unnecessary.

A 2-digits number has 2 = 2! lexicographic permutations

A 3-digits number has 6 = 3! lexicographic permutations

Hence, n-digits number has n! lexicographic permutations

Here we have ten digits , range from 0 to 9 to form a 10-digits number (include 0 leading).

So the total lexicographic permutations of this number would be 10! (or 9!*10) . It means every digit in a n-digits number has (n-1)! lexicographic permutation. (*)

The 1st lexicographic permutation is 0123456789, the 362881th (9!+1) lexicographic permutation is 1023456789, the 725761th is 2013456789 (9!*2 +1 ) , the 1088641th is 301456789, and so on.

1000000 is bigger than 725761 but smaller than 1088641 , we sure that the first number will be 2, leave out 013456789.

n = 1000000 – 725761 = 274239

s = 2

From (*), we now that in order to know which number is the first number in the list 013456789, we must divide n = 274239 to (k-1)!, which is (9-1)! = 8!, the result is 6.8, we round it to 6. the 6th number in the list 013456789 (0 is the 0th number), is 7, leave out 01345689

n = 274239 – 6*8! = 32319

s = 27

Like we did above, n = 32319 divide to (k-1)!, which is (8-1)! = 7!, the result is 6.4, but we round it to 6. the 6th number in the list 01345689 is 8, leave out 0134569

n = 32319 – 6*7! = 2079

s = 278

Continue, n = 2079 / 6! = 2.9, round to 2. The 2th number in the list 0134569 is 3, leave out 014569

n = 2079-2*6! = 639

s =2783

Continue, n = 639 / 5!  = 5.3, round to 5. The 5th number in the list 014569 is 9, leave out 01456

n = 639 – 5*5! = 39

s = 27839

Continue, n = 39/4! = 1.6, round to 1, the 1th number in the list 01456 is 1, leave out 0456

n = 39 – 1*4! = 15

s = 278391

Continue, n = 15/3! = 2.5, round to 2, the 2th number in the list 0456 is 5 , leave out 046

n = 15- 2*3! = 3

s = 2783915

Continue, n = 3/2! = 1.5, round to 1, the 1th number in the list 046 is 4, leave out 06

n = 3 – 1*2! = 1

s = 27839154

Continue, n = 1/1! = 1, the 1th number in the list 06 is 6

n = 1 – 1*1! = 0

s = 278395146

the list now has only one number, 0. We just need take 0 and add to the last of s.

The thing I wrote above is also what the program produces. So I don’t give you the code (which obviously you can write by yourself :> )

Update: which n bigger than 10!, you have to make it smaller.

For example we have n=  10.000.000, divide it to 10! = 2.8, round to 2. Then n = n – 2*10!. Now it’s smaller than 10!. It means you can apply the above algorithm.

Advertisements