計劃中的笛卡爾積

Question

我一直在試圖做一個函數，返回n套的笛卡爾乘積，在Dr方案中，集合以列表的形式給出，我一直被困在這一整天，我想從一些準則開始。

----稍後編輯-----

這裏是我想出瞭解決方案，我敢肯定，這是迄今爲止最efficent或整齊的不是，但我只STUDING方案3周對我來說很簡單。

Answer 1

;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 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 nested loops and recursion

Answer 3

這是我的第一個解決方案（次優）：

#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 4

這裏有一個簡潔的實現，它也被設計爲減少由此產生的結構在內存中的大小，通過共享組件列表的尾部。它使用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 5

我想我的手在製作中H韋弗（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又名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))