読者です 読者をやめる 読者になる 読者になる

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

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

たぶん、これが最後。
その3のheightという補助変数を無くし、全てのmulti-indexからなるシーケンスall-multi-indexを作りました。

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

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

(defn first-nonzero [mi]
  (first 
    (filter 
      #(not (zero? (mi %)))
      (range (count mi)))))

(defn incr-multi-index [mi]
  (let [lasti (- (count mi) 1)
        i (first-nonzero mi)]
    (if (or (nil? i) (= i lasti))
      (assoc mi
        lasti 0
        0     (+ 1 (mi lasti)))
      (assoc mi
        (+ i 1) (+ 1 (mi (+ i 1)))
        i 0
        0       (- (mi i) 1)))))

(defn multi-index-get [seqs mi]
  (if (every? identity (map (fn[s i] (has-nth s i)) seqs mi))
    (apply vector (map (fn[s i] (nth s i)) seqs mi))
    nil))

(deftest test-multi-index-get
  (is (= (multi-index-get ["abc" "xyz" "0123"] [0 0 0])
         [\a \x \0]))
  (is (= (multi-index-get ["abc" "xyz" "0123"] [5 0 0])
         nil)))

(defn new-multi-index [size]
  (vec (repeat size 0)))

(defn multi-index-height [mi]
  (apply + mi))

(defn multi-index-out-of-range [seqs mi]
  (every? not (map #(has-nth %1 %2) seqs mi)))

(defn all-multi-indexes [size]
  (iterate incr-multi-index (new-multi-index size)))

(defn product [& seqs]
  (if (empty? seqs)
    (list [])
    (let []
      (filter (complement nil?)
        (map #(multi-index-get seqs %)
          (take-while #(not (multi-index-out-of-range seqs %))
            (all-multi-indexes (count seqs))))))))

(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))))))
広告を非表示にする