Lexicographic permutations
Problem 024: 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?
Solution:
>"ddd"**1v
vp129p11-<
>v>v v < v < > v >\1-\vv p14+1g14<
>21g:1+|>|>21g0\>:1-:#^_v>*\:#^_$:| >31p 141p >31g41g*11g`!|
$ >$1 ^ > p68*v>$1^ |-"x" g0:\<\1<g14 <
@ > #^0#<#v0#,+ #<$ v> >1+\:| 1
^p12-1g12p11-*-1g14g13g11 <^\"x"\-"0"g0:>#- #1 #$ #< ^
Explanation:
This is a really nice problem - and I kinda like the solution.
If we think about the ordered numbers we can see that the first few start with 0, the next with 1 and so on ...
We can also see that there are 8! possible numbers that start with 0 (or any other digit).
So if 1 * 8! <= (1000000 - 0) the result starts with 0. Otherwise if 2 * 8! <= (1000000 - 0), etc.
Then after we got our first digit (2) we can similar calculate the second with 1 * 7! <= (1000000 - 2 * 8!), 2 * 7! <= (1000000 - 2 * 8!) ...
The last thing we have to be aware of is that this method yields us to the "n-th digit of the remaining digits". So if we got the 6th digit for our second calculation its in fact 7, because we already used 2.
The program now does exactly these calculations, you can see in the top row the already used digits (they are crossed out).
All in all this program pretty fast - they could really do another version of this problem with bigger numbers.
| Interpreter steps: | 3 499 |
| Execution time (BefunExec): | 31ms (0.11 MHz) |
| Program size: | 61 x 8 (fully conform befunge-93) |
| Solution: | 2783915460 |
| Solved at: | 2014-09-16 |