CODEWITHSUNDEEP
racket
ryman
ryman

Reputation: 1

Can any one convert this code to Pseudo Code

#lang racket
(define (cartesian-product . lists)
(foldr (lambda (xs ys)
            (append-map (lambda (x)
                          (map (lambda (y)
                                 (cons x y))
                               ys))
                        xs))
          '(())
          lists))

(cartesian-product '(1 2 3) '(5 6))

I have racket lang code, that calculate cartesian product of two sets or lists, I don't understand the code well, can any one convert code to pseudo code.

Upvotes: 0

Views: 134

Answers (1)

Atharva Shukla
Atharva Shukla

Reputation: 2137

The function corresponds to this definition of cartesian products.

  1. The dot . in the argument means that lists will collect all the arguments (in a list) no matter how many are passed in.

  2. How to call such a function? Use apply. It applies a function using items from a list as the arguments: (apply f (list x-1 ... x-n)) = (f x-1 ... x-n)

  3. foldr is just an abstraction over the natural recursion on lists

; my-foldr : [X Y] [X Y -> Y] Y [List-of X] -> Y
; applies fun from right to left to each item in lx and base
(define (my-foldr combine base lx)
  (cond [(empty? lx) base]
        [else (combine (first lx) (my-foldr func base (rest lx)))]))

Applying the simplifications from 1), 2) and 3) and turning the "combine" function in foldr to a separate helper:

(define (cartesian-product2 . lists)
  (cond [(empty? lists) '(())]
        [else (combine-cartesian (first lists)
                                 (apply cartesian-product2 (rest lists)))]))

(define (combine-cartesian fst cart-rst)
  (append-map (lambda (x)
                (map (lambda (y)
                       (cons x y))
                     cart-rst))
              fst))

(cartesian-product2 '(1 2 3) '(5 6))

Let's think about "what" combine-cartesian does: it simply converts a n-1-ary cartesian product to a n-ary cartesian product.

We want:

(cartesian-product '(1 2) '(3 4) '(5 6))
; = 
; '((1 3 5) (1 3 6) (1 4 5) (1 4 6) (2 3 5) (2 3 6) (2 4 5) (2 4 6))

We have (first lists) = '(1 2) and the result of the recursive call (induction):

(cartesian-product '(3 4) '(5 6))
; = 
; '((3 5) (3 6) (4 5) (4 6))

To go from what we have (result of the recursion) to what we want, we need to cons 1 onto every element, and cons 2 onto every element, and append those lists. Generalizing this, we get a simpler reformulation of the combine function using nested loops:

(define (combine-cartesian fst cart)
  (apply append
         (for/list ([elem-fst fst])
           (for/list ([elem-cart cart])
             (cons elem-fst elem-cart)))))

To add a dimension, we consed every element of (first lists) onto every element of the cartesian product of the rest.

Pseudocode:

  cartesian product <- takes in 0 or more lists to compute the set of all 
                       ordered pairs
    - cartesian product of no list is a list containing an empty list.
    - otherwise: take the cartesian product of all but one list
                 and add each element of that one list to every 
                 element of the cartesian product and put all 
                 those lists together.

Upvotes: 1

Related Questions