潛在的無限序列的有限序列的笛卡爾乘積

Question

的問題

我需要創建，鑑於潛在的無限序列的有限序列時，它產生是他們的「笛卡爾積」的序列的功能。

即給定的順序

'((1 2) (3 4)) 

功能產生（的某種排序）：

'((1 3) (1 4) (2 3) (2 4) 

重要，爲每一位p在笛卡爾積ps名單，必須有一些自然數n，例如(= p (last (take n ps)))。或者，非正式地說，您只需要遍歷有限數量的序列以到達其中的任何元素。

這個條件在處理無限列表時變得很重要。在Haskell

在Haskell

解決方案，這是我會怎麼做它：

interleave   :: [a] -> [a] -> [a] 
interleave [] ys  = ys 
interleave (x:xs) ys = x : interleave ys xs 

combine :: [[a]] -> [[a]] 
combine = foldr prod [[]] 
    where 
    prod xs css = foldr1 interleave [ [x:cs | cs <- css] | x <- xs] 

，把它你會得到如下：Clojure中

combine [[0..] [0..]] = [[0,0,0],[1,0,0],[,1,0],[2,0,0],[0,0,1],[1,1,0],... 

解決方案

所以我試圖在Clojure中複製它，就像這樣（這幾乎是一個直接的t ranslation）：

(defn interleave 
    "Returns a lazy sequence of the interleavings of sequences `xs` and `ys` 
    (both potentially infinite), leaving no elements discarded." 
    [xs ys] 
    (lazy-seq 
    (if-let [[x & xs*] (seq xs)] 
     (cons x (interleave ys xs*)) 
     ys))) 

(defn interleave* 
    "Converts a sequence of potentially infinite sequences into its lazy 
    interleaving." 
    [xss] 
    (lazy-seq 
    (when-let [[xs & xss*] (seq xss)] 
     (interleave xs (interleave* xss*))))) 

(defn combine 
    "Takes a finite sequence of potentially infinite sequences, and combines 
    them to produce a possibly infinite sequence of their cartesian product." 
    [xss] 
    (if-let [[xs & xss*] (seq xss)] 
    (interleave* 
     (for [x xs] 
     (for [cs (combine xss*)] 
      (lazy-seq (cons x cs))))) 
    '(()))) 

但是當我運行：

(take 1 (combine [(range) (range)])) 

我得到：

StackOverflowError cfg.util/combine/iter--3464--3468/fn--3469/fn--3470/iter--3471--3475/fn--3476 

所以，我怎麼讓它偷懶足夠，以免造成堆棧溢出？真的，我不明白Clojure的惰性序列模型是如何工作的，這是主要問題。

Answer 1

我認爲您的解決方案可能是算法棘手，重建子序列一次又一次，就像簡單的斐波那契函數一樣：

(defn fib [n] 
    (case n 
    (0N 1N) n 
    (+ (fib (- n 1)) (fib (- n 2))))) 

...重新計算其先例。

在任何情況下，在(range)和(range)笛卡爾乘積尋找[100 10]：

(first (filter #{[100 10]} (combine [(range) (range)]))) 

...沒有在合理的時間內返回。

---

我可以爲您提供一個更快，但不太優雅的解決方案。

首先，一對夫婦的工具：

Something from @amalloy計算有限序列的笛卡爾乘積：

(defn cart [colls] 
    (if (empty? colls) 
    '(()) 
    (for [x (first colls) 
      more (cart (rest colls))] 
     (cons x more)))) 

改編自Clojure的食譜的一種功能的映射的值映射：

(defn map-vals [f m] (zipmap (keys m) (map f (vals m)))) 

現在我們想要的功能，我叫enum-cart，一個š它枚舉的笛卡爾積甚至無限序列：

(defn enum-cart [colls] 
    (let [ind-colls (into (sorted-map) (map-indexed (fn [n s] [n (seq s)]) colls))  
     entries ((fn tins [ss] (let [ss (select-keys ss (map key (filter val ss)))] 
           (lazy-seq 
            (if (seq ss) 
            (concat 
             (map-vals first ss) 
             (tins (map-vals next ss))))))) 
        ind-colls) 
     seens (reductions 
       (fn [a [n x]] (update-in a [n] conj x)) 
       (vec (repeat (count colls) [])) 
       entries)] 
    (mapcat 
     (fn [sv [n x]] (cart (assoc sv n [x]))) 
     seens entries))) 

的想法是生成的條目的索引序列中，去輪非耗盡序列。由此我們生成了我們已經從每個序列中看到的伴隨序列。我們將這兩者結合起來，用新的元素的自由笛卡爾積與其他序列的結果一起生成。答案就是這些免費產品的連接。

例如

(enum-cart [(range 3) (range 10 15)]) 

...產生

((0 10) 
(1 10) 
(0 11) 
(1 11) 
(2 10) 
(2 11) 
(0 12) 
(1 12) 
(2 12) 
(0 13) 
(1 13) 
(2 13) 
(0 14) 
(1 14) 
(2 14)) 

而且

(first (filter #{[100 10]} (enum-cart [(range) (range)]))) 
;(100 10) 

...返回或多或少瞬間。

---

注

• 這是更好地克努特或其他地方做了什麼？我沒有訪問 它。
• 最後一個未耗盡的序列無需保留，因爲沒有其他 其他人可以使用它。

Answer 2

所以，我想通了。這個問題是一個微妙而令人沮喪的問題。這個問題源於我執行的解構，基本上每個函數都是這樣的：我使用這種成語：[x & xs*] (seq xs)，然而，這實現了xs*的第一個元素，以及實現了x。這種行爲類似於如果您要分別使用first和next來獲取列表的頭部和尾部，您會看到的行爲。

使用first/rest，而不是用這種方式固定堆棧溢出解構：

(defn interleave 
    "Returns a lazy sequence of the interleavings of sequences `xs` and `ys` 
    (both potentially infinite), leaving no elements discarded." 
    [xs ys] 
    (lazy-seq 
    (if-let [xs* (seq xs)] 
     (cons (first xs*) (interleave ys (rest xs*))) 
     ys))) 

(defn interleave* 
    "Converts a sequence of potentially infinite sequences into its lazy 
    interleaving." 
    [xss] 
    (lazy-seq 
    (when-let [xss* (seq xss)] 
     (interleave (first xss*) 
        (interleave* (rest xss*)))))) 

(defn combine 
    "Takes a finite sequence of potentially infinite sequences, and combines 
    them to produce a possibly infinite sequence of their cartesian product." 
    [xss] 
    (if-let [xss* (seq xss)] 
    (interleave* 
     (for [x (first xss*)] 
     (for [cs (combine (rest xss*))] 
      (lazy-seq (cons x cs))))) 
    '(()))) 

並運行它，我們得到：

(= (take 5 (combine [(range) (range) (range)])) 
    '((0 0 0) (1 0 0) (0 1 0) (2 0 0) (0 0 1)))