Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Cartesian product in Scheme

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.

like image 880
John Retallack Avatar asked Mar 20 '10 23:03

John Retallack


People also ask

What is Cartesian product with example?

In mathematics, the Cartesian Product of sets A and B is defined as the set of all ordered pairs (x, y) such that x belongs to A and y belongs to B. For example, if A = {1, 2} and B = {3, 4, 5}, then the Cartesian Product of A and B is {(1, 3), (1, 4), (1, 5), (2, 3), (2, 4), (2, 5)}.

What is Cartesian product in economics?

Definition of Cartesian product : a set that is constructed from two given sets and comprises all pairs of elements such that the first element of the pair is from the first set and the second is from the second set.

What is AxB?

AxB = {(a,b) | a ∈ A and b ∈ B}. Cartesian Product is also known as Cross Product. Consider Set A = { 3, 4, 5} B = {x, y} then AxB is given by. A. 3 4 5.


2 Answers

Here's a concise implementation that is also designed to minimize the size of the resulting structure in memory, by sharing the tails of the component lists. It uses SRFI-1.

(define (cartesian-product . lists)
  (fold-right (lambda (xs ys)
                (append-map (lambda (x)
                              (map (lambda (y)
                                     (cons x y))
                                   ys))
                            xs))
              '(())
              lists))
like image 68
Mark H Weaver Avatar answered Sep 26 '22 05:09

Mark H Weaver


;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: Scheme/Lisp nested loops and recursion

like image 39
Yuval Adam Avatar answered Sep 23 '22 05:09

Yuval Adam