The millionth lexiconical permutation

Here's a problem from Project Euler:

#24 Lexicographic permutations - Project Euler

A website dedicated to the fascinating world of mathematics and programming

Project EulerColin Hughes

ok. Let

b : base, aka the set of numbers.

n: the index of the lexicographical permutation we want.

N: total number of lexicographical permutations of the given set.

m: index of subset of lexicographical permutations, (where the leading digit is the same before ticking over)
M: total number of subsets of lexicographical permutations. Which is simply b
a = number of permutations in a subset m.

So, for two digits we have 2 permutations. And for 3 digits there are 6.

and for 4 digits:

Ok, cool cool cool cool.

We can kinda see a trend - for each group, there'd be permutation(b-1, b-1) number of permutations in each subset of b, for example

for b=4 there are permutation(3, 3)= 6 permutations in each subset m.

So lets say we want to find out what the 21st lexicographical permutation of 0,1,2,3 is. We might make it easier by first finding which subset n is in. Let's define this function:

function WhichSubsetIsTargetIndexIn(base, targetIndex) {
N = permutation(base, base)

return floor(base * (targetIndex/N))

}

so for n = 21, we know m is 3. Great! As noted before, the first digit of the mth group is m, so we only have permutation(b-1, b-1) permutations to calculate now.

the index relative to the subset (offset index which we could call j) would simply be n - (n//a), so if we want to find n = 21, we want to find the lexicographical permutation for 21 - (21//6) = 3rd index in the subgroup that begins with 3, ending some mix of remaining number set of b, {0,1,2}. We know that the smallest in this set would be the second-leading digit for permutation(b-1-1,b-1-1) = permutation(2, 2) = 2 times.

and so we can deduce that for the jth index, the number should be of the kth index of the set {0,1,2} (which in this case the set indices k directly correspond to the number itself, but you can imagine for example if m = 2, the set is {0,1,3} instead) is how many times over can permutation(b-1-1,b-1-1) fit in j:

k = j // permutation(b-1-1,b-1-1)

so since j = 3 and b = 4, k = 3//2 = 1, and index 1 points to 1 of the set {0,1,2}.

so we have the lexicographic permutation 31xx. The remaining number set of b is now {0, 2}, and the same goes:

k = j//permutation(b-1-1-1, b-1-1-1) = 3//permutation(1,1) = 3//1 = 3, which simply means it wraps around the set – imagine the set repeated : {0,2,0,2...} so k=3 means the corresponding number is 2. Thus the 21st lexicographic permutation of the set {b=4} is 3120.

Now for the millionth lexicographic permutation of set {b=10}...

Ok, cool cool cool cool.

b = 10
n = 1,000,000
N = permutation(10, 10) = 3,628,800
m = WhichSubsetIsTargetIndexIn(b,n) = floor( 10 * (1000000 / 3628800)) = floor(2.7557319224) = 2

So we have 2,xxx,xxx,xxx.
There are 10 groups of 362,880 permutations. a = 362,880
The remaining set is {0,1,3,4,5,6,7,8,9}.
The offset index j is 1000000 - (1000000//362880) = 999998
k1 = j // permutation(b-1-1, b-1-1) = 999998 // permutation(8, 8) = 999998 // 40320 = 24 i.e. 24 % len({0,1,3,4,5,6,7,8,9}) = 6
=> 2,7xx,xxx,xxx
k2 = j // permutation(b-1-1-1, b-1-1-1) = 999998 // permutation(7, 7) = 999998 // 5040 = 198 i.e. k2 = 198 % len({0,1,3,4,5,6,8,9}) = 6
=> 2,78x,xxx,xxx
k3 = 999998 // permutation(6,6) = 1388 i.e k3 = 1388 % len({0,1,3,4,5,6,9}) = 2
=> 2,783,xxx,xxx
k4 = 999998 // permutation(5,5) % len({0,1,4,5,6,9}) = 5
=> 2,783,9xx,xxx
k5 = 999998 // permutation(4,4) % len({0,1,4,5,6}) = 5
=> 2,783,91x,xxx
k6 = 999998 // permutation(3,3) % len({0,4,5,6}) = 2
=> 2,783,915,xxx
k7 = 999998 // permutation(2,2) % len({0,4,6}) = 1
=> 2,783,915,4xx
k8 = 999998 // permutation(1,1) % len({0,6}) = 0
=> 2,783,915,40x
k9 = 999998 // permutation(0,0) % len({6}) = 1
=> 2,783,915,406

The millionth lexicographical permutation of {0,1,2,3,4,5,6,7,8,9} is 2,783,915,406!

I checked the answer and I was wrong. It is 2,783,915,460. I messed up in the end - at k8, and k9, there are 2 digits left, and the 2nd place digit will always tick over because in binary the first place digit only takes two before the overflow changes the 2nd place digit - the permutation would always be permutation(2,2) from k8 onwards to k9.