(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:

```
(defun add-num (digit-list)
(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)))
(nreverse (add-num revlist))))
(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.**