Y箱

順列の1000000番目はなに？って問題だけど、樹形図を考えてこんな手順にした。

先頭に0があるやつは、 9! で 362880通り。1000000をこえない
先頭に1があるやつも、 9! で 362880通り。1000000をこえない
先頭に2があるやつは、 9! で 362880通りで、1000000をこえてしまうから、先頭は2
次は20で始まるやつは、8! で 40320通りで1000000をこえない
....って順に求めていく。

;;
;; Problem 24  : 2011/5/10
;; "Elapsed time: 1.543492 msecs"  
(def fact-tree
     [362880 40320 5040 720 120 24 6 2 1])

(use 'clojure.contrib.math)

(loop [fact-tree fact-tree
       num-list [0 1 2 3 4 5 6 7 8 9]
       remains (dec 1000000)
       res-list ()]
  (if (empty? fact-tree)
    (concat (reverse res-list) num-list)
    (let [div (floor (/ remains (first fact-tree)))
          tgt-num (nth num-list div)]
      (recur (rest fact-tree)
             (remove #(= % tgt-num) num-list)
             (rem remains (first fact-tree))
             (cons tgt-num res-list)))))
;;