Lexicographic Permutations

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?

The task here involves determining the specific permutation in the lexicographic ordering of all possible permutations of the digits 0 through 9. Essentially, you’re asking for the “millionth term” in this sequence. To approach the problem systematically, we can use the concept of factorial.

A factorial, expressed with the notation n!, is the product of an integer and all positive integers less than it. For instance, 5! = 5*4*3*2*1 = 120.

For the digits 0 through 9, we have 10 digits, the total number of permutations is 10!, which equals 3,628,800 possible permutations. But we’re not looking for all permutations, we’re only interested in finding an efficient way to identify the one-millionth permutation.

The permutations can be divided into 10 sets where the first digit ranges from 0-9, each set containing 9! (or 362,880) permutations.

The first set of permutations start with 0, the second with 1, the third with 2, and so on. Given that each set contains 362,880 permutations, we can deduce that the 1,000,000th permutation will lie in the 3rd set (which starts with 2) because 2*362,880 is 725,760, which is less than 1,000,000 and 3*362,880 is 1,088,640, which surpasses the desired index.

After removing the first two sets (725,760 permutations), we’re left with needing to find the (1,000,000 – 725,760) = 274,240th permutation within the third set (that starts with 2).

Next, we do the same process with the remaining 9 digits (0, 1, 3, 4, 5, 6, 7, 8, 9). There are 9! = 362,880 permutations and we can divide them into 9 sets, each having 8! (or 40,320) permutations. We find that the 274,240th permutation will lie in the 7th set (which starts with 7), because 6*40,320 is 241,920, which is less than 274,240 and 7*40,320 is 282,240, which is greater than 274,240.

Subtracting the first six sets from our target, we’re left with needing to find the (274,240 – 241,920) = 32,320th permutation within that seventh set (that starts with seven).

We continue this process until there’s only one digit remaining. The complete sequence in order would be 2, 7, 8, 3, 9, 1, 5, 4, 6, 0.

So, in the lexicographic ordering of the digits 0, 1, 2, 3, 4, 5, 6, 7, 8 and 9, the one-millionth term will be the permutation 2783915460.

More Answers: