Skip to content

Instantly share code, notes, and snippets.

@kohyama
Last active December 10, 2015 02:58
Show Gist options
  • Save kohyama/4371543 to your computer and use it in GitHub Desktop.
Save kohyama/4371543 to your computer and use it in GitHub Desktop.
Project Euler Problem 24
(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
(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
@kohyama
Copy link
Author

kohyama commented Dec 28, 2012

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

@ypsilon-takai
Copy link

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

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

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

@kohyama
Copy link
Author

kohyama commented Dec 28, 2012

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

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

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment