潜在的无限序列的有限序列的笛卡尔乘积

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)))