I was trying to solve the lexicographic permutation problem yesterday and out of plain curiosity, I decided to carry out some research on Wikipedia. I found this thing called factoradic which is a factorial-based number system. I conveniently used this thing to approach the solution and decided to work out how factoradic actually worked.
I decided to assign this thing called a rank to the permutation. So assuming that we have 9 digits [1, 2, 3, 4, 5, 6, 7, 8, 9] and that we need to find the 2092nd lexicographic permutation, we begin as follows.
Assume that the first digit is 1 (the smallest of the digits we have). There are 8 remaining digits. So, the maximum number starting with one should occupy the 40320th position ( 8! = 40320 ). Since 2092 < 40320, we know that the first digit is 1.
Now, we place the next smallest digit beside 1. We have 7 digits left and the maximum number whose 1st two digits are 1 and 2 occupies the position 5040. 2092 < 5040 and hence, we can confirm that the first two digits are 1 and 2 indeed. We now append 3 at the end of our current permutation. We have 6 other digits and hence the maximum number of numbers we can get with 123 in front is 720. Now, 2092 > 720 and this means that the number placed 2092 is greater than “123xxxxxx” where the “x” represent the digits we have not come across yet.
We now replace 3 by 4 (the permutation becomes “124xxxxxx”). The maximum number of numbers is 720 + 720 = 1440 which is still lesser than 2092 and we can safely replace 4 by 5 and the maximum position we get is 1440 + 720 = 2160 which is greater than 2092. So the permutation now looks like “125xxxxxx”.
Placing the minimum number from the remaining numbers after 5 in our permutation (the number is 3), we get something like “1253xxxxx”. The maximum rank is 1440 + 5! = 1440 + 120 = 1570. This falls short of 2092. So we replace 3 by 4, the maximum position is 1440 + 120 + 120 = 1690. Still short, put 6 there, the maximum position is 1810. Put 7 there, the rank becomes 1930. Put 8 there and the rank becomes 2050. Still short, replace 8 by 9 and 2170 is what we get. So our permutation now looks like “1259xxxxx”.
It should be straightforward from here on. Proceed in this fashion and you should end up at 125963784.
If you look at the above procedure and note down the number of replacements, you get the factoradic! It is as simple as that.
So, I whipped up a small script to get the factoradic:
First a straightforward factorial function:
if n==0 or n==1:
return 1
else:
return n * factorial(n-1)
Then, a function that greedily chooses the digit of the factoradic:
for i in xrange(position, -1, -1):
fact = factorial(position) * i
if fact < decimal_num:
return i, decimal_num – fact
else:
continue
Finally a function that generates the entire factoradic:
factoradic = []
num = decimal_num
for i in xrange(length-1, -1, -1):
bag = genFact(num, i)
factoradic.append(bag[0])
num = bag[1]
return factoradic
Testing this on 2092 with an initial number containing 9 elements, we get:
[0,0,2,5,2,0,1,1,0]
Which leads us to the answer from my calculations.
I decided to solve the project euler problem (number 24) on lexicographic permutations using this algorithm and the factoradic I obtained was [2, 6, 6, 2, 5, 1, 2, 1, 1, 0] which leads us to 2783915460 which turned out to be the right answer.
You can obtain the factoradic generating script at http://shriphani.com/scripts/factoradic.py .
Essay Time! — Shriphani’s Weblog // Sep 26, 2008 at 8:41 pm
[...] Lexicographic permutation; [...]
well, i read somewhere that in factorial number system, pi is 11.11111111.. and e(exponential) is 10.10101010.. could you get it confirmed?