Kartesisches Produkt in Scheme

Question

Ich habe versucht, eine Funktion zu tun, die das kartesische Produkt von n-Sets zurückgibt, in Dr Scheme, die Sätze sind als eine Liste von Listen angegeben, ich habe den ganzen Tag fest, ich möchte ein paar Richtlinien als wo zu beginnen.

---- SPÄTER EDIT -----

Hier ist die Lösung kam ich mit, ich bin sicher, dass es nicht weit von der die meisten efficent oder ordentlich, aber ich studiere nur Schema für 3 Wochen, also sei einfach zu mir.

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

Quelle: Scheme/Lisp nested loops and recursion

Answer 3

Hier ist meine erste Lösung (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)) 

Grundsätzlich wollen Sie das Produkt des Produkts aus den Listen zu erzeugen.

Answer 4

Hier ist eine kurze Implementierung, die auch entworfen, um die Größe der resultierenden Struktur im Speicher zu minimieren, indem sie den Schwanz der Komponentenlisten teilen. Es verwendet 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

habe ich versucht, meine Hand auf die elegante Lösung von Mark H Weaver machen (https://stackoverflow.com/a/20591545/7666) leichter zu verstehen.

Es ist immer noch die gleiche Logik, aber die Operationen benennen.

Das obige ist in wisp-syntax alias SRFI-119. Die äquivalente Ebene Schema ist:

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