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?
Permalink: http://projecteuler.net/problem=24
Instead of developing permutation function we use math.combinatorics
permutations function does the trick
(->> (range 10)
(comb/permutations)
(drop (dec 1000000))
(first)
(apply str)))
That was easy! It returns result in just 3 seconds, what is acceptable.
If you need to solve this problem faster, observe the interesting properties:
1 - 0123456789
2 - 0123456798
...
9! - 0987654321
9!+1 - 1023456789
...
2*9! - 1987654320
2*9!+1 - 2013456789
...
3*9! - 2987654310
3*9!+1 - 3012456789
3*9! is greater than 1000000, so we stop on the 2*9! permuations and guessed first number, it’s 2
Proceed the same way and you’ve got the idea. On each factorial permutation step, when you guessed the number remove it from further permutations and decrement the factorial
(let [! (fn [n] (reduce * (range 1 (inc n))))]
(loop [available-digits (range 10)
num 1000000
current-digit 0
init 9
result []]
(let [f (! init)]
(cond
(= 0 init)
(apply str (concat result available-digits))
(< f num) (recur available-digits
(- num f)
(inc current-digit)
init
result)
:else (recur (concat (take current-digit available-digits)
(drop (inc current-digit) available-digits))
num
0
(dec init)
(conj result (nth available-digits current-digit)))))))
Solution is less readable, but time is just 5 msecs. There is always tradeoff.