数を並びかえる(1)

参考文献 : プログラミング Clojure 第2版、(Stuart Halloway and Aaron Bedra 著、川合史朗 訳、オーム社)

正月に本屋でこの本をみつけて面白いと思ったので買ってしまったのです。

この記事のタイトルは 「clojure を学ぶ」等でも良かったかもしれない。何かテーマがあったほうがやり易いというくらいの意味しかない。

次の関数は頻繁に使うので最初に置いておく。

(defn range1-n [n] (range 1 (inc n)))

やりたいのは以下のようなこと :

(for [i0 (range1-n 3) i1 (range1-n 3) i2 (range1-n 3) :when (= (count (set [i0 i1 i2])) 3)] [i0 i1 i2])
=>
([1 2 3] [1 3 2] [2 1 3] [2 3 1] [3 1 2] [3 2 1])

こういうのが任意の n で欲しい。

(defn permutation [coll]
  (let [coll (into [] coll)
        n (count coll)
        idx (into [] (for [j (range n)] (symbol (str "i" j))))
        lst (take n (iterate identity coll)) ; vector にする必要なし
        args (into [] (interleave idx lst))]
    (eval `(for ~(conj args :when `(= (count (set ~idx)) ~n)) ~idx))))

マクロなら eval は必要ないが (permutation (range 1 6)) のように使いたいので eval を使って関数にした。

lisp と違うのは , のかわりに ~ を使うことだけ。

into [] のところは冗長な感じがするが、clojure は基本がシーケンス(リストやベクトルなどのデータ構造の統一概念)で、関数の仮引数などは特に(シーケンスの1つである)ベクトルでないといけないので仕方ないようだ。このケースでは into []apply vector でも同じことになる。

試してみる :

(permutation [:a :b :c :d])
=>
([:a :b :c :d] [:a :b :d :c] [:a :c :b :d] [:a :c :d :b] [:a :d :b :c] [:a :d :c :b]
[:b :a :c :d] [:b :a :d :c] [:b :c :a :d] [:b :c :d :a] [:b :d :a :c] [:b :d :c :a]
[:c :a :b :d] [:c :a :d :b] [:c :b :a :d] [:c :b :d :a] [:c :d :a :b] [:c :d :b :a]
[:d :a :b :c] [:d :a :c :b] [:d :b :a :c] [:d :b :c :a] [:d :c :a :b] [:d :c :b :a])

(count *1)
=>
24

\( 1 \mapsto 2, 2 \mapsto 1, 3 \mapsto 3\) というような関数が欲しいとする :

((fn [i] ([2 1 3] (dec i))) 1)
=> 2
((fn [i] ([2 1 3] (dec i))) 2)
=> 1
((fn [i] ([2 1 3] (dec i))) 3)
=> 3

funcall なしで lambda を呼べるのが良い。

これを map に渡せば

(map (fn [i] ([2 1 3] (dec i))) [1 2 3])
=> (2 1 3)

となる。

置換をこうやって関数にしてやればいいが、これだとやや不満で関数内部に置いた [2 1 3] が見えなくなってしまう。([1 2 3] に作用させれば取り出せるが)

そこでこんな風にクロージャにする。

(defn make-fn [p]
  (let [p (atom p)]
    (fn
      ([] @p)
      ([i] (@p (dec i))))))
      
(def a (make-fn [2 1 3]))

(a)
=>
[2 1 3]

(a 1)
=>
2

無名関数でも引数の数に応じて場合分けのように書ける。

すべての置換を上のような関数に変換する :

(defn make-fns [permutation]
  (mapv #(make-fn %) permutation))

(defn symmetric-group [n]
  (make-fns (permutation (range1-n n))))
  
(symmetric-group 3)
=> 
[#function[user/make-fn/fn--49822]
#function[user/make-fn/fn--49822]
#function[user/make-fn/fn--49822]
#function[user/make-fn/fn--49822]
#function[user/make-fn/fn--49822]
#function[user/make-fn/fn--49822]]

これで \(S_{3}\) が得られた。

使ってみる :

(def S3 (symmetric-group 3))

(doseq [f S3] (println (map f [1 2 3])))
=>
(1 2 3)
(1 3 2)
(2 1 3)
(2 3 1)
(3 1 2)
(3 2 1)

(doseq [f S3] (println (f)))
=>
[1 2 3]
[1 3 2]
[2 1 3]
[2 3 1]
[3 1 2]
[3 2 1]

(symmetric-group 20) なら 2432902008176640000 個の関数を一挙に得たことになる。

これを repl で直接打つと大変なことになるのでやらないほうが良い。

余談 :

(dotimes [_ 10] (time (symmetric-group 5)))
=>
"Elapsed time: 11.844575 msecs"
"Elapsed time: 9.075536 msecs"
"Elapsed time: 6.124669 msecs"
"Elapsed time: 6.56306 msecs"
"Elapsed time: 5.446622 msecs"
"Elapsed time: 6.575427 msecs"
"Elapsed time: 5.933537 msecs"
"Elapsed time: 5.385878 msecs"
"Elapsed time: 11.593396 msecs"
"Elapsed time: 5.342361 msecs"

(dotimes [_ 10] (time (symmetric-group 20)))
=>
"Elapsed time: 30.094795 msecs"
"Elapsed time: 26.712697 msecs"
"Elapsed time: 28.283736 msecs"
"Elapsed time: 26.234125 msecs"
"Elapsed time: 26.656523 msecs"
"Elapsed time: 28.128561 msecs"
"Elapsed time: 29.462102 msecs"
"Elapsed time: 25.283257 msecs"
"Elapsed time: 27.413928 msecs"
"Elapsed time: 27.933447 msecs"

どうも小さい n では安定しない。

広告を非表示にする