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.
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)}.
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.
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.
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))
;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
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With