Project Euler Problem 24 asks us to find the millionth lexicographic permutation of the numbers 1 through 9. As near as I can tell, “lexicographic” means “in dictionary order”, or simply “sorted”.

The first attempt that I wrote was as simple but slightly buggy:

```
(defn all-but-nth [coll n]
"Returns a list of all items in coll except the nth item."
(concat (take (dec n) coll) (drop n coll)))
(defn permutations [coll]
(if (= 1 (count coll))
[coll]
(apply concat (for [i (range 1 (inc (count coll)))]
(map (fn [a] (concat [(nth coll (dec i))] a))
(lazy-seq (permutations (all-but-nth coll i))))))))
(defn euler-24 [c]
(nth (permutations [0 1 2 3 4 5 6 7 8 9]) (dec c)))
(time (euler-24 1000)) ;; "Elapsed time: 45.33433 msecs"
(time (euler-24 10000)) ;; "Elapsed time: 544.487392 msecs"
(time (euler-24 100000)) ;; "Elapsed time: 7374.706124 msecs"
(time (euler-24 1000000)) ;; Heap overflow, and very slow
```

Unfortunately, my simple definition was clearly requiring the entire sequence to remain in memory, eventually causing a heap overflow on the slow computer that I was using. Also, the `permutations`

function was unnecessarily complex, so I rewrote the above solution as:

```
(defn all-but-nth [coll n]
"Returns a list of all items in coll except the nth item. (zero indexed)"
(lazy-cat (take n coll) (drop (inc n) coll)))
(defn permutations [coll]
"Returns a lazy list of all permutations of coll."
(if (= 1 (count coll))
[coll]
(for [i (range (count coll))
p (permutations (all-but-nth coll i))]
(lazy-cat [(nth coll i)] p))))
(defn euler-24 [c]
(nth (permutations [0 1 2 3 4 5 6 7 8 9]) (dec c)))
(time (euler-24 1000000)) ;; "Elapsed time: 110979.128041 msecs"
```

Much better! Though it only took 20 seconds on my fast computer, on my slow computer this still took about two minutes to solve. Surely there must be a way to jump directly to the nth permutation without computing all of the intermediate values? After thinking about how many possible permutations there exist given n items, I came up with the following algorithm which essentially performs modulus and remainder to find the nth lexicographic permutation directly:

```
(defn factorial [n]
(reduce * (range 2 (inc n))))
(defn num-permutations [coll]
(factorial (dec (count coll))))
(defn nth-permutation [coll n]
(if (= 1 (count coll))
[(nth coll 0)]
(let [f (num-permutations coll)
x (quot n f)]
(concat [(nth coll x)]
(nth-permutation (all-but-nth coll x)
(- n (* x f)))))))
(defn euler-24-fast [n]
(nth-permutation [0 1 2 3 4 5 6 7 8 9] (dec n)))
(time (euler-24-fast 1000000)) ;; Elapsed time: 0.361691 msecs"
```

Pretty good performance! Also, if we really needed to compute and process the first 1,000,000 elements, this algorithm could easily be `partition`

‘d and `pmap`

‘d across multiple CPUs much more easily than the naive first algorithm.