scheme - Scheme中的笛卡尔积

Question

我一直在尝试做一个返回 n 个集合的笛卡尔积的函数，在 Dr Scheme 中，集合作为列表列表给出，我整天都被困在这个问题上，我想要一些指导方针开始。

----以后编辑-----

这是我想出的解决方案，我敢肯定它不是迄今为止最有效或最整洁的，但我只学习了 3 周的 Scheme，所以请放轻松。

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

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

资料来源：Scheme/Lisp 嵌套循环和递归

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

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

基本上你想生产列表产品的产品。

Answer 5

我试着让 Mark H Weaver ( https://stackoverflow.com/a/20591545/7666 ) 的优雅解决方案更容易理解。

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 aka SRFI-119。等效的普通方案是：

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

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