3つ以上の集合の直積を求めるプログラム その３

可変個の集合から、直積の集合を作る - チキン煮込みチーズミックス4辛
Re: 3つ以上の集合の直積を求めるプログラム - ちなみに
3つ以上の集合の直積を求めるプログラム - ようこそ＼(^o^)／ゲストさん
3つ以上の集合の直積を求めるプログラム - None is None is None
3つ以上の集合の直積を求めるプログラム その２ - None is None is None

昨夜書いたバージョンは、無限シーケンスの直積を扱えません。

例えば、

=> (product (iterate inc 0) (iterate inc 0))
((0 0) (0 1) (0 2) (0 3) (0 4) (0 5) (0 6) (0 7) (0 8) (0 9) (0 10) (0 11) (0 12) (0 13) (0 14) (0 15) (0 16) (0 17) (0 18) (0 19) (0 20) (0 21) (0 22) (0 23) (0 24) (0 25) (0 26) (0 27) (0 28) (0 29) (0 30) (0 31) (0 32) (0 33) (0 34) (0 35) (0 36) (0 37) (0 38) (0 39) ...

第一成分が0のままで、どうやっても(1 0)に辿り着きません。

そこで、(0 0) (0 1) (1 0) (0 2) (1 1) (2 0) ...と辿るように改良しました。

(ns product
  (:use clojure.contrib.seq-utils
        clojure.contrib.test-is
        clojure.contrib.combinatorics))

(defn has-nth [seq n]
  (boolean (nthnext seq n)))

(defn zip [seq1 seq2]
  (map #(vector %1 %2) seq1 seq2))

(defn multi-indexes-with-height [h size]
  (cond
    (zero? size)
      (if (= h 0)
        [[]]
        [])
    (= 1 size)
      [[h]]
    :else
      (for [i     (range (+ h 1))
            rests (multi-indexes-with-height (- h i) (- size 1))]
        (cons i rests))))

(defn tuples-of-height [h seqs]
  (for [multi-index (multi-indexes-with-height h (count seqs))
        :when (every? (fn [[s i]] (has-nth s i)) (zip seqs multi-index))]
    (map (fn [[s i]] (nth s i)) (zip seqs multi-index))))

(defn chain [seqs]
  (for [seq seqs
        v seq]
    v))

(defn product [& seqs]
  (chain
    (take-while not-empty
      (map #(tuples-of-height % seqs) (iterate inc 0)))))

(deftest test-multi-indexes-with-height
  (is (= (multi-indexes-with-height 0 0) 
          [[]]))
  (is (= (multi-indexes-with-height 1 0)
          []))
  (is (= (multi-indexes-with-height 0 1)
          [[0]]))
  (is (= (multi-indexes-with-height 2 1) 
          [[2]])))

(deftest test-tuples-of-height
  (is (= (tuples-of-height 0 []) 
        [[]]))
  (is (= (tuples-of-height 1 [])
        []))
  (is (= (tuples-of-height 0 ["abc"])
        [[\a]]))
  (is (= (tuples-of-height 1 ["abc"])
        [[\b]]))
  (is (= (tuples-of-height 4 ["abc"])
        []))
  (is (= (tuples-of-height 0 ["abc" "xyz"] )
      [[\a \x]])))

(deftest test-product
  (let [numbers [1 2 3]]
    (doseq [i (range 1)]
      (is (= (sort (apply cartesian-product (repeat i numbers))) 
             (sort (apply product           (repeat i numbers))))))))

(deftest test-product-inf
  (let [all-nums (iterate inc 0)
        p (product all-nums all-nums all-nums)]
    (doseq [i [0 1 2]]
      (is (some #(= 5 (nth % i)) (take 100 p))))))

セミナーの予習もせずに何やってるんだろ。