Sản phẩm Descartes trong Đề án

Question

Tôi đã cố gắng thực hiện một chức năng trả về Sản phẩm Descartes của n bộ, trong Dr Scheme, các bộ được đưa ra như một danh sách các danh sách, tôi đã bị mắc kẹt ở đây cả ngày, tôi muốn một số hướng dẫn về nơi bắt đầu.

---- EDIT SAU -----

Dưới đây là giải pháp tôi đưa ra, tôi chắc chắn rằng nó không phải đến nay là efficent nhất hoặc gọn gàng nhưng tôi chỉ studing Scheme cho 3 tuần nên dễ dàng với tôi.

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

Nguồn: Scheme/Lisp nested loops and recursion

Answer 3

Đây là giải pháp đầu tiên của tôi (tối ưu):

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

Về cơ bản bạn muốn sản xuất các sản phẩm của các sản phẩm của các danh sách.

Answer 4

Đây là triển khai ngắn gọn cũng được thiết kế để giảm thiểu kích thước của cấu trúc kết quả trong bộ nhớ, bằng cách chia sẻ đuôi của danh sách thành phần. Nó sử dụng 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

Tôi đã cố gắng thực hiện giải pháp thanh lịch của Mark H Weaver (https://stackoverflow.com/a/20591545/7666) dễ hiểu hơn.

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 

Nó vẫn là cùng một logic, nhưng đặt tên cho các hoạt động.

Ở trên là trong wisp-syntax aka SRFI-119. Sơ đồ đồng bằng tương đương là:

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