Cartesian product in Scheme

Question

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.

Alfy

Similar: #1658729 – Vacant

yes ,it's part of homework,I don't necessarily need the code,I want some guidelines – Alfy

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

Alfy

Answer 2

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

Beersheba

Answer 3

;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

Vacant

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 – Alfy

Combine the 2-set version with fold to get an n-set version. In general for associative operations, you can define an n argument version in terms of the 2 argument version with fold. – Sena

Answer 4

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.

Torrey

Also if you look at the question that Yuval posted Paul Hollingsworth posted a well documented version, albeit not working in plt-scheme. #1658729 – Torrey

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

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... ;) – Torrey

Answer 5

I tried my hand at making the elegant solution of Mark H Weaver (https://mcmap.net/q/1020737/-cartesian-product-in-scheme) easier to understand.

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

It is still the same logic, but naming the operations.

The above is in wisp-syntax aka SRFI-119. The equivalent plain Scheme is:

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

Mispleading

Answer 6

Here is my answer, I'm doing some homework. Using Guile on Emacs.

(define product                                                               
  (lambda (los1 los2)                                                         
    (if (or (null? los1) (null? los2))                                        
        '()                                                                   
        (cons (list (car los1) (car los2))                                    
              (append (product (list (car los1)) (cdr los2))                  
                    (product (cdr los1)  los2))))                             
                                                                              
        )                                                                     
    )                                                                         
                                                                              
(product '(a b c ) '(x y)) 

;; Result:
=> ((a x) (a y) (b x) (b y) (c x) (c y))  

Rod