Project Euler Problem 24

pep024+.clj

(require '[clojure.test :refer (is)])

(defn pms
  "Permutations lexicographic by index."
  [[a & [b & [c & _]] :as ls]]
  (cond
    (nil? a) '()
    (nil? b) `(~a)
    (nil? c) `((~a ~b) (~b ~a))
    :else (mapcat (fn [h] (map (fn [r] (cons h r))
                               (lazy-seq (pms (remove #(= % h) ls)))))
                  ls)))

(is (= (pms '(a b c))
       '((a b c) (a c b) (b a c) (b c a) (c a b) (c b a))))

(defn pep024+
  ([] (pep024+ "0123456789" 1000000))
  ([digits n] (apply str (nth (pms digits) (dec n)))))

(is (= (pep024+ "012" 5) "201"))

(time (pep024+)) ; "Elapsed time: 14099.017 msecs" in my environment

pep024.clj

(require '[clojure.test :refer (is)])

;; dependent on [org.clojure/math.combinatorics "0.0.3"]
(require '[clojure.math.combinatorics :refer (permutations)])

(defn pep024
  ([] (pep024 "0123456789" 1000000))
  ([digits n] (apply str (nth (permutations digits) (dec n)))))

(is (= (pep024 "012" 5) "201"))

(time (pep024)) ; "Elapsed time: 983.816 msecs" in my environment

#clojure 入門者向け勉強会 #mitori_clj 第四週担当分
Project Euler Problem 24
「数字 0, 1, 2, 3, 4, 5, 6, 7, 8 および 9 を辞書順に並べた順列の 1,000,000 番目は何か」とのことです.

インデクス辞書順な順列が与えられてしまうとすることが無い (pep024.clj) ので, 一応自分でも書いてみました (pms in pep024+.clj)

文字数減らしたい性なので (list (list a b) (list b a)) を ``((~a ~b) (~b ~a))` のように書いています.
lazy-seq したいのでなければベクタ使うところですが.

拙 pms は math.combinatorics の permutations と比べると10倍以上遅いです.
math.combinatorics のソース 読んで勉強します.

別解です。

最初に解いたときに、permutations関数を知らなくて、考え出した方法です。実際の数列を求めないで答えを出しています。

https://gist.github.com/4387213

permutations関数、自分も挑戦してみようかな。

@ypsilon-takai 別解ありがとうございます. 御 gist の方にコメントしましたが, これは凄いすばらしい解法！！
効率の良い方法をいろいろ考えてみる態度を見習いたいです.

効率の良い方法をいろいろ考えてみる態度

たしか、このときは、自作のpermutationsのような関数が、あまりに遅くて、1分どころでなかったので、しぶしぶだったような気がします。(笑

でも、学生のころに、「可視化すると何かが見える」ということを教えられたし経験もしたので、問題にあたるときは図を書いてみるという習慣はありますね。
仕事でもかなり役にたっています。

「可視化すると何かが見える」

なるほど.
確かに樹形図を実際に書いてみると「こっから下は書かなくても大きさが分かればいいじゃない？」ってなりそうですね.
見習います.