Skip to content

Instantly share code, notes, and snippets.

@kohyama kohyama/pep024+.clj
Last active Dec 10, 2015

Embed
What would you like to do?
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

This comment has been minimized.

Copy link
Owner Author

commented Dec 25, 2012

#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 のソース 読んで勉強します.

@ypsilon-takai

This comment has been minimized.

Copy link

commented Dec 27, 2012

別解です。

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

https://gist.github.com/4387213

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

@kohyama

This comment has been minimized.

Copy link
Owner Author

commented Dec 28, 2012

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

@ypsilon-takai

This comment has been minimized.

Copy link

commented Dec 28, 2012

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

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

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

@kohyama

This comment has been minimized.

Copy link
Owner Author

commented Dec 28, 2012

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

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

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.