Find the inverse of the method to find the nth lexicographic logical permutation

combinatoricsinverse functionpermutationspuzzle

I'm looking for a proper method to find the nth logical permutation of a particular sequence that is able to return the desired permutation. For example, for a sequence 1234567890, the 100,001st logical permutation is 1469037825, as calculated by:

To find the first digit,

Since there are 10 digits, fixing the first digit, there are 9! ways to permute the rest.

$\ 100 001 – 0(9!) = 100 001$ (As 1×9! is larger than 100001)

Hence the first digit is the 0th element in the list of digits 1234567890, i.e. $\ 1$

To find the second digit

$\ 100 001 – 2(8!) = 19361$

Hence the second digit is the 2nd element in the list of digits 234567890, i.e. $\ 4$ (counting from 0)

To find the third digit

$\ 19361 – 3(7!) = 4241$

Hence the third digit is the 3rd element in the list of digits 23567890, i.e. $\ 6$ (counting from 0)

And so forth

$\ 4241 – 5(6!) = 641 $ 5th in 2357890 is $\ 9$

$\ 641- 5(5!) = 41$ 5th in 235780 is $\ 0$

$\ 41 – 1(4!) = 17 $ 1st in 23578 is $\ 3$

$\ 17 – 2(3!) = 5$ 2nd in 2578 is $\ 7$

$\ 5 – 2(2!) = 1 $ 2nd in 258 is $\ 8$

$\ 1 – 0(1!) = 1 $ 0th in 25 is $\ 2$ (Remainder has to be more than 0)

Hence last digit remaining is $\ 5$

The 100,001st permutation of 1234567890 is 1469037825

How would I then be able to find the value of n, such than the nth permutation of $\ 1469037825$ is $\ 1234567890?$

Best Answer

1469037825

1234567890
^----------> 0 * 9!
234567890
  ^--------> 2 * 8!
23567890
   ^-------> 3 * 7!
2357890
     ^-----> 5 * 6!
235780
     ^-----> 5 * 5!
23578
 ^---------> 1 * 4!
2578
  ^--------> 2 * 3!
258
  ^--------> 2 * 2!
25
^----------> 0 * 1!

$$0\cdot9!+2\cdot8!+3\cdot7!+5\cdot6!+5\cdot5!+1\cdot4!+2\cdot3!+2\cdot2!+0\cdot1!+1=100001$$ This shows that $1469037825$ is the $100,001^\text{st}$ lexicographic permutation of $1234567890$

1234567890

1469037825
^----------> 0 * 9!
469037825
       ^---> 7 * 8!
46903785
    ^------> 4 * 7!
4690785
^----------> 0 * 6!
690785
     ^-----> 5 * 5!
69078
^----------> 0 * 4!
9078
  ^--------> 2 * 3!
908
  ^--------> 2 * 2!
90
^----------> 0 * 1!

$$0\cdot9!+7\cdot8!+4\cdot7!+0\cdot6!+5\cdot5!+0\cdot4!+2\cdot3!+2\cdot2!+0\cdot1!+1=303017$$ This shows that $1234567890$ is the $303,017^\text{th}$ lexicographic permutation of $1469037825$

Related Question