在Scheme中的笛卡尔积

Question

我一直在尝试编写一个函数，该函数返回n个集合的笛卡尔积。在Dr Scheme中，这些集合以列表的形式给出，我已经陷入困境了一整天，希望能得到一些指导。

----稍后编辑-----

这是我想出的解决方案，我相信它远非最有效或最整洁，但我只学了3周的Scheme，所以请对我宽容点。

- John Retallack

---

类似：https://dev59.com/LErSa4cB1Zd3GeqPTRWh - Yuval Adam

是的，这是作业的一部分，我不一定需要代码，我想要一些指导方针。 - John Retallack

Answer 1

这是一种简洁的实现，同时旨在通过共享组件列表的尾部来最小化内存中结果结构的大小。它使用SRFI-1。

(define (cartesian-product . lists)
  (fold-right (lambda (xs ys)
                (append-map (lambda (x)
                              (map (lambda (y)
                                     (cons x y))
                                   ys))
                            xs))
              '(())
              lists))

- Mark H Weaver

Answer 2

;compute the list of the (x,y) for y in l
(define (pairs x l)
  (define (aux accu x l)
    (if (null? l)
        accu
        (let ((y (car l))
              (tail (cdr l)))
          (aux (cons (cons x y) accu) x tail))))
  (aux '() x l))

(define (cartesian-product l m)   
  (define (aux accu l)
    (if (null? l) 
        accu
        (let ((x (car l)) 
              (tail (cdr l)))
          (aux (append (pairs x m) accu) tail))))
  (aux '() l))

Source: Scheme/Lisp nested loops and recursion

- Yuval Adam

---

这有什么帮助吗？这是两个集合的笛卡尔积，我的问题是针对n个集合的，我知道如何计算两个集合的笛卡尔积，但我不知道如何计算n个集合的。 - John Retallack

将2集版本与fold结合，得到n集版本。通常对于可交换操作，您可以通过fold在2个参数版本的基础上定义一个n参数版本。 - soegaard

Answer 3

  ;returs a list wich looks like ((nr l[0]) (nr l[1])......)
  (define cart-1(λ(l nr)
      (if (null? l) 
             l 
             (append (list (list nr (car l))) (cart-1 (cdr l) nr)))))

;Cartesian product for 2 lists
(define cart-2(λ(l1 l2)
                (if(null? l2) 
             '() 
             (append (cart-1 l1 (car l2)) (cart-2 l1 (cdr l2))))))

 ;flattens a list containg sublists
(define flatten
(λ(from)
 (cond [(null? from) from]
      [(list? (car from)) (append (flatten (car from)) (flatten (cdr from)))]
      [else (cons (car from) (flatten (cdr from)))])}) 

;applys flatten to every element of l
(define flat
(λ(l)
(if(null? l)
l
(cons (flatten (car l)) (flat (cdr l))))))

;computes Cartesian product for a list of lists by applying cart-2
(define cart
(lambda (liste aux)
 (if (null? liste)
  aux
  (cart (cdr liste) (cart-2 (car liste) aux)))))


(define (cart-n l) (flat (cart (cdr l ) (car l))))

- John Retallack

Answer 4

这是我的第一个解决方案（不够优化）：

#lang scheme
(define (cartesian-product . lofl)
  (define (cartOf2 l1 l2)
    (foldl 
     (lambda (x res) 
       (append 
        (foldl 
         (lambda (y acc) (cons (cons x y) acc)) 
         '() l2) res))
     '() l1))
  (foldl cartOf2 (first lofl) (rest lofl)))

(cartesian-product '(1 2) '(3 4) '(5 6))

基本上，您希望生成列表的乘积的乘积。

- Jake

---

此外，如果您查看Yuval发布的问题，Paul Hollingsworth发布了一个文档完备的版本，尽管它不能在plt-scheme中工作。https://dev59.com/LErSa4cB1Zd3GeqPTRWh#1677386 - Jake

关于 Cipher 的解决方案，您可以采取什么措施以获取未加点的列表？ - anna-k

我认为你的意思是，你不想要结果是一个不恰当的列表（或嵌套对），而是想要一个列表的列表。如果是这样，最简单/最简单/最糟糕的方法就是将(cons x y)更改为(cons x (if (list? y) y (list y)))。我不喜欢这个方法。但这不是我的作业... ;) - Jake

Answer 5

我尝试着让 Mark H Weaver 的优雅解决方案（https://dev59.com/MkzSa4cB1Zd3GeqPorL0#20591545）更易于理解。

import : srfi srfi-1
define : cartesian-product . lists
    define : product-of-two xs ys
         define : cons-on-each-ys x
            map : lambda (y) (cons x y)
                . ys
         append-map cons-on-each-ys
                  . xs
    fold-right product-of-two '(()) lists

这仍然是相同的逻辑，只是给操作命名。

上面的内容来自于 wisp-syntax 或 SRFI-119。等价的普通Scheme代码如下：

(import (srfi srfi-1))
(define (cartesian-product . lists)
    (define (product-of-two xs ys)
         (define (cons-on-each-ys x)
            (map (lambda (y) (cons x y))
                ys))
         (append-map cons-on-each-ys
                  xs))
    (fold-right product-of-two '(()) lists))

- Arne Babenhauserheide

Answer 6

这是我的答案，我正在做一些作业。在Emacs上使用Guile。

(define product                                                               
  (lambda (los1 los2)                                                         
    (if (or (null? los1) (null? los2))                                        
        '()                                                                   
        (cons (list (car los1) (car los2))                                    
              (append (product (list (car los1)) (cdr los2))                  
                    (product (cdr los1)  los2))))                             
                                                                              
        )                                                                     
    )                                                                         
                                                                              
(product '(a b c ) '(x y)) 

;; Result:
=> ((a x) (a y) (b x) (b y) (c x) (c y))  

- spikeyang