Prodotto cartesiano in schema

Question

Ho cercato di eseguire una funzione che restituisce il prodotto cartesiano di n set, in Dr Scheme, i set sono indicati come un elenco di elenchi, sono rimasto bloccato per tutto il giorno, vorrebbe alcune linee guida come da dove cominciare.

---- DOPO EDIT -----

Ecco la soluzione mi è venuta, sono sicuro che non è di gran lunga il più efficiente o ordinata ma sto solo studiando Schema di 3 settimane, quindi sii facile con me.

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

Fonte: Scheme/Lisp nested loops and recursion

Answer 3

Qui è la mia prima soluzione (non ottimale):

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

In sostanza si vuole produrre il prodotto del prodotto delle liste.

Answer 4

Ecco un'implementazione concisa che è stato progettato anche per ridurre al minimo le dimensioni della struttura risultante in memoria, condividendo le code delle liste dei componenti. Usa 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

ho provato la mia mano a rendere la soluzione elegante di Marco H Weaver (https://stackoverflow.com/a/20591545/7666) più facile da capire.

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 

È sempre la stessa logica, ma denominazione delle operazioni.

Quanto sopra riportato è wisp-syntax aka SRFI-119. L'equivalente schema semplice è:

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