2010-03-20 25 views
5

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.Kartesisches Produkt in Scheme

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

+0

Ist das Hausaufgaben? –

+0

Ähnlich: http://stackoverflow.com/questions/1658229/scheme-lisp-nested-loops-and-recursion –

+0

ja, es ist Teil der Hausaufgaben, ich brauche nicht unbedingt den Code, ich möchte einige Richtlinien –

Antwort

3
;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)))) 
4
;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

+1

wie ist Das soll das Cartesian Produkt von 2 Sätzen sein, meine Frage war für n Sätze, ich kann es für zwei Sätze berechnen, ich weiß nicht, wie man es für n –

+2

bildet Kombiniert die 2-Satzversion mit fold, um eine n-set Version zu erhalten. Im Allgemeinen können Sie für assoziative Operationen eine n-Argument-Version in Form der 2-Argument-Version mit falten definieren. – soegaard

2

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.

+0

Auch wenn Sie sich die Frage ansehen, die Yuval gepostet hat, hat Paul Hollingsworth eine gut dokumentierte Version gepostet, die allerdings nicht im plt-Schema funktioniert. http://stackoverflow.com/questions/1658229/scheme-lisp-nested-loops-and-recursion/1677386#1677386 – Jake

+0

In Bezug auf die Cipher's Lösung, was können Sie tun, um die Liste der Listen ungeschlagen zu bekommen? –

+1

Ich denke, was Sie meinen, ist, dass Sie nicht wollen, dass das Ergebnis eine Liste von falschen Listen (oder verschachtelten Paaren) ist, sondern Sie wollen eine Liste von Listen. Wenn dies der Fall ist, wäre der einfachste/einfachste/schlechteste Weg, dies zu erreichen, die Änderung (cons x y) zu (cons x (if (list y y) (list y))). Ich mag das nicht. Aber es ist nicht meine Hausaufgabe ...;) – Jake

6

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

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