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.