views:

332

answers:

4

I've been trying to do a function that returns the Cartesian Product of n sets,in Dr Scheme,the sets are given as a list of lists,I've been stuck at this all day,I would like a few guidelines as where to start.

----LATER EDIT -----

Here is the solution I came up with,I'm sure that it's not by far the most efficent or neat but I'm only studing Scheme for 3 weeks so be easy on me.

A: 
;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))

Source: http://stackoverflow.com/questions/1658229/scheme-lisp-nested-loops-and-recursion/1658894#1658894

Yuval A
how is this supposed to help ?This is the Cartesian Product of 2 sets,my question was for n sets,I know how to compute it for two sets,I don't know how to make it for n
John Retallack
+1  A: 

Here is my first solution (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))

Basically you want to produce the product of the product of the lists.

Cipher
Also if you look at the question that Yuval posted Paul Hollingsworth posted a well documented version, albeit not working in plt-scheme. http://stackoverflow.com/questions/1658229/scheme-lisp-nested-loops-and-recursion/1677386#1677386
Cipher
A: 

Hello! Regarding the Cipher's solution, what can you do in order to get the list of lists undotted?

anna-k
I think what you mean is that you don't want the result to be a list of improper lists (or nested pairs), rather you want a list of lists. If so, the easiest/simplest/worst way to accomplish this would be to change (cons x y) to (cons x (if (list? y) y (list y))). I don't like this. But its not my homework... ;)
Cipher
A: 
  ;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))))
John Retallack