# euler 24 permutations

Feb 8, 2015

(The fact that this turned out to be a long story is ridiculous, but perhaps it’ll be useful to someone else)

The idea here is intuitive: given say `0`, `1` and `2`, we can immediately come up with the following orderings:

``````012
021
102
120
201
210
``````

The problem here is to find the millionth permutation of `0`, `1`, `2`, `3`, `4`, `5`, `6`, `7`, `8`, `9`.

The first way is to cheat and work it out with pen-and-paper, upon which you soon realize that there are cycles for each set of numbers. E.g. for two numbers we would have 2 possible orderings (`01` and `10`), for three we have the ones shown above, etc, and this is because for `n` numbers we have `n!` combinations. Right, that’s obvious. But the next step is to see that within each block of `n!`, there are `n` blocks of size `(n-1)!`, where the first digit is the same, which means we have a straightforward way of reducing the problem of size `n` to a problem of size `n-1`.

As an example, to find the fifth permutation in the example above, we would see that it involves two cycles of two digits each, and then halfway through a single cycle. So we can come up with the first digit being `2`, and the next digit being the second of the remaining digits (i.e. `1`), and we’re finally left with `0`.

(Note: Argh … This sentence is wrong! But I didn’t realize that until later)

So I wrote the code for this, and I used Ocaml because I’m a complete n00b at it.

``````let rec fact n =
if n = 0 then 1
else n * fact (n - 1)

let perm_total = 1_000_000;;

let get_perm total index =
let fact_index = fact index in
total / (fact_index), total mod fact_index

let rec get_all_perms total index_size =
let rec get_next_perm total index_size perm_list =
if index_size = 0 then perm_list
else match get_perm total index_size with
| p, new_total -> get_next_perm new_total (index_size - 1) (p :: perm_list)
in List.rev (get_next_perm total index_size [])

let rec digits_list n lst =
if n = 0 then (0 :: lst)
else digits_list (n - 1) (n :: lst)

let remove_digit digit lst =
List.filter (fun x -> x <> digit) lst

let rec get_next_perm_digit perm_list digit_list pdlist =
if List.length perm_list = 0 then pdlist
else let p = List.hd perm_list in
let d = List.nth digit_list p in
get_next_perm_digit (List.tl perm_list) (remove_digit d digit_list) (d :: pdlist)

let rec get_perm_digits perm_list =
let digits = digits_list (List.length perm_list) [] in
List.rev (get_next_perm_digit perm_list digits [])

let euler24 = get_perm_digits (get_all_perms perm_total 9);;
``````

Yes, the names are terrible. Many of the started out as nested functions which I pulled into the top-level to test separately. Anyway, the point is … the answer was wrong.

Ok, I thought, I must’ve screwed up in the Ocaml-ness of my solution. So I rewrote it thusly:

``````(defun fact (n)
(if (= n 1)
1
(* n (fact (1- n)))))

(defparameter *total* 1000000)

(defun get-perm (total index)
(let ((f (fact index)))
(truncate total f)))

(defun get-next-perm (total index-size perm-list)
(if (= index-size 0)
(cons 0 perm-list)
(multiple-value-bind (p new_total)
(get-perm total index-size)
(get-next-perm new_total (1- index-size) (cons p perm-list)))))

(defun get-all-perms (total index-size)
(reverse (get-next-perm total index-size '())))

(defun digits-list (n)
(loop for i from 0 to n
collect i))

(defun get-next-perm-digit (perm-list digit-list p-d-list)
(if (null perm-list)
p-d-list
(let* ((p (first perm-list))
(d (nth p digit-list)))
(get-next-perm-digit (rest perm-list)
(remove d digit-list)
(cons d p-d-list)))))

(defun get-perm-digits (perm-list)
(let ((digits (digits-list (1- (length perm-list)))))
(reverse (get-next-perm-digit perm-list digits '()))))

(defun euler-24 ()
(get-perm-digits (get-all-perms *total* 9)))
``````

The same answer popped out – which means I was successful at my translation – but it was still the wrong answer. In the initial few seconds of denial, I refreshed the Project Euler page and tried again. No luck.

Now it was time for desperate measures, so I came up with this brute force solution:

``````(defun list->number (list)
(reduce (lambda (x y) (+ (* x 10) y)) list))

(defun number->list (n)
(do ((tempn n (floor (/ tempn 10)))
(digits '() (cons (mod tempn 10) digits)))
((= tempn 0) digits)))

(defun has-digits (n digit-list)
(let ((nlist (number->list n)))
(not (set-difference digit-list nlist))))

(defun brute-force-next-permutation (digit-list)
(let ((n (list->number digit-list)))
(do ((trynum (1+ n) (1+ trynum)))
((has-digits trynum digit-list) (number->list trynum))
(format t "Trying ~A~%" trynum))))
``````

…. which wasn’t quite right either, since it skipped the leading zero in our lists. This one seemed to work:

``````
(let ((sum (1+ (first digit-list))))
(if (< sum 10)
(cons sum (rest digit-list))
(cons (mod sum 10) (add-num (rest digit-list))))))

(defun next-number (digit-list)
(let ((revlist (reverse digit-list)))

(defun brute-force-next-permutation (digit-list)
(do ((trynum (next-number digit-list) (next-number trynum)))
((not (set-difference digit-list trynum)) trynum)))

(defun brute-force-nth-permutation (digit-list n)
(do ((i 1 (1+ i))
(trynum digit-list (brute-force-next-permutation trynum)))
((= i n) trynum)))
``````

So I set that running with `(brute-force-nth-permutation '(0 1 2 3 4 5 6 7 8 9) 1000000)`, and it looked like it was clearly going to take a while.

At this point I was really depressed, since I couldn’t figure out what was wrong with the initial approach which was so straightforward … and then I realized that I was probably off by one.

So I took the answer submitted earlier, and entered the next permutation. Nope. Ok, what about the previous one? That worked!

(Note: To circle back to the ‘trivial’ example at the top of the post: I didn’t catch myself talking about the fifth permutation as being 0,1,2,3,4,5 – so I was really talking about the sixth permutation …)

Later, the (inefficient) brute-force computation terminated in `1668` seconds, and happily, the answers matched. I tried the previous code with a small modification:

``````(defun euler-24 ()
(get-perm-digits (get-all-perms (1- *total*) 9)))
``````

… and it gave the same answer (and obviously, so did the Ocaml version). So a happy ending to this story, but a painful reminder of the fact that there are only two hard problems in computer science: naming, caching, and off-by-one errors.