無限シーケンスから組み合わせ生成
組み合わせ生成関数（無限シーケンス対応版）を作ってみました。
;; Ver.1 (defn- combinations* [xs combs] (when-first [x xs] (let [new-combs (map (fn [c] (conj c x)), combs)] (lazy-cat new-combs (combinations* (rest xs) (concat combs new-combs)))))) (defn combinations ([xs] (let [combs '([])] (concat combs (combinations* xs combs)))) ([n xs] (->> (combinations xs) (filter #(-> (count %) (= n))))))
♯まずは有限シーケンスで
;; １引数で評価 (combinations [1 2 3 4]) ;;=> ([] [1] [2] [1 2] [3] [1 3] [2 3] [1 2 3] [4] [1 4] ;; [2 4] [1 2 4] [3 4] [1 3 4] [2 3 4] [1 2 3 4])
１引数で評価すると、引数をシーケンスとして受取り、可能な組み合わせを列挙します。組み合わせの要素数も可能なパターンを全て列挙します。上の例では、0〜4個の組み合わせがベクタとして生成されています。
;; ２引数で評価 (combinations 3 [1 2 3 4]) ;;=> ([1 2 3] [1 2 4] [1 3 4] [2 3 4])
２引数で評価すると、第１引数が組み合わせの要素数になります。一般に組み合わせというとこちらの形式が期待されるでしょう。
内部的には、１引数で combinations を評価してその結果に対し、要素数で filter をかけているだけです。
１引数で評価した combinations の出力はあまり馴染みがありませんが、意外と出番はありそうな気がします。
例えば「４つの整数においてそれぞれ高々１つずつ選んで掛け合せた時に生成される合成数のパターン」は次のように求めることが出来ます。
(->> (combinations [2 3 5 7]), (map #(apply * %))) ;;=> (1 2 3 6 5 10 15 30 7 14 21 42 35 70 105 210)
評価結果の第１項の「１」は要素数０のリストの全要素の積です。clojure の式で書くと (*) で、掛け算の単位元を表しています。
♯論理的背景
１引数の combinations の評価結果の形式は、無限シーケンスを扱う時に重要となります。
ここで少し数学っぽい表現を使って数式を定義してみます。
- n 項のシーケンスを S(n) とする。
- S(n) の第 n 項 を A(n) とする。
- S(n) の要素 (つまりA(0)〜A(n) ) で可能な組み合わせの集合を C(n) とする。
- C(n) が内包する全ての組み合わせパターンにおいて、それぞれに対して A(n+1) を追加することで出来る組み合わせの集合を CA(n+1) とする。
最後の定義がちょっと分かりにくいですが、具体例でいうと。
S(n) = (1 2) A(n+1) = 3 C(n) = ([] [1] [2] [1 2]) CA(n+1) = ([3] [1 3] [2 3] [1 2 3])
という感じです。C(n) の全ての項に対し、新たに A(n+1) を付け加えています。
以上のように定義すると C(n) と C(n+1) の関係は、
- C(n+1) = C(n) ∪ CA(n+1)
という漸化式で表せます。このような漸化式の形に表すことができれば、たとえ n が無限に発散しようとも、漸次的に部分集合を得続けることが可能になります。*1
♯無限シーケンスでの使用例
(->> (combinations (range)), (take 30)) ;;=> ([] [0] [1] [0 1] [2] [0 2] [1 2] [0 1 2] [3] [0 3] [1 3] ;; [0 1 3] [2 3] [0 2 3] [1 2 3] [0 1 2 3] [4] [0 4] [1 4] ;; [0 1 4] [2 4] [0 2 4] [1 2 4] [0 1 2 4] [3 4] [0 3 4] ;; [1 3 4] [0 1 3 4] [2 3 4] [0 2 3 4]) (->> (combinations 5 (range)), (take 1000)) ;;=> ([0 1 2 3 4] [0 1 2 3 5] [0 1 2 4 5] [0 1 3 4 5] [0 2 3 4 5] ;; [1 2 3 4 5] [0 1 2 3 6] [0 1 2 4 6] [0 1 3 4 6] [0 2 3 4 6] ;; -- 中略 -- ;; [0 7 8 9 12] [1 7 8 9 12] [2 7 8 9 12] [3 7 8 9 12] [4 7 8 9 12])
;; 9のつく素数9つで構成されるパターンを999個 (use '[clojure.contrib.lazy-seqs :only (primes)]) (->> primes (filter #(->> % str (some (partial = \9)))) (combinations 9) (take 999)) ;;=> ([19 29 59 79 89 97 109 139 149] ;; [19 29 59 79 89 97 109 139 179] ;; [19 29 59 79 89 97 109 149 179] ;; -- 中略 -- ;; [59 89 97 109 139 149 179 193 199])
;; 男女３人の組み合わせを生成 (def xs (->> (range) (mapcat #(list (str "男" %) (str "女" %))))) (take 10 xs) ;;=> ("男0" "女0" "男1" "女1" "男2" "女2" "男3" "女3" "男4" "女4") (->> (combinations 3 xs) (take 100)) ;;=> (["男0" "女0" "男1"] ["男0" "女0" "女1"] ["男0" "男1" "女1"] ;; ["女0" "男1" "女1"] ["男0" "女0" "男2"] ["男0" "男1" "男2"] ;; ["女0" "男1" "男2"] ["男0" "女1" "男2"] ["女0" "女1" "男2"] ;; -- 中略 -- ;; ["女1" "女2" "女4"] ["男2" "女2" "女4"] ["男0" "男3" "女4"])
この稿、続く
