Produkt kartezjański na Schemacie

Question

Próbowałem wykonać funkcję, która zwraca iloczyn kartezjański n zestawów, w Dr Scheme, zestawy są podane jako lista list, utknąłem w tym cały dzień, I Chciałbym kilka wskazówek, od czego zacząć.

---- PÓŹNIEJ EDIT -----

Oto rozwiązanie wymyśliłem, jestem pewien, że nie jest to zdecydowanie najbardziej skuteczny i schludny, ale jestem tylko studiuje Programu dla 3 tygodnie, więc bądź dla mnie łatwy.

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

Źródło: Scheme/Lisp nested loops and recursion

Answer 3

Oto moje pierwsze rozwiązanie (suboptimal):

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

Zasadniczo chcesz produkować produkt produktu z listy.

Answer 4

Oto zwięzły realizacja, która jest również zaprojektowany, aby zminimalizować wielkość powstałej struktury w pamięci, dzieląc ogony list składowych. Używa 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

próbowałem swoich sił w dokonaniu eleganckie rozwiązanie Mark H Weavera (https://stackoverflow.com/a/20591545/7666) łatwiejszy do zrozumienia.

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 

Jest to wciąż ta sama logika, ale nazywanie operacji.

Powyższe informacje znajdują się w wisp-syntax znany również jako SRFI-119. Równoważny prosty schemat to:

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