2014-09-16

# Problem 024: Lexicographic permutations

Description:

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:
v0123456789
>"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 #\$ #<  ^
Start
??
Pause
Reset
Output:
Stack:   (0)

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

made with vanilla PHP and MySQL, no frameworks, no bootstrap, no unnecessary* javascript