Summary

Generating the Cartesian Product of multiple lists is very useful for iteration and exhausting their combinations.

One might use the Cartesian Product when constructing a test matrix, or when generating code.

I will generate the Cartesian Product in as many languages as I can.

Plan

  • Add implementations for more languages
  • Make it optionally recursive
    • Implement nested lists (not just multi-list) for each language
    • Treat a non-list as a list of length 1
    • Sometimes you don’t want the Cartesian Product to be recursive because you may want to deal in lists rather than merely strings or ints. i.e. You want the products of the Cartesian Product to be lists; Lists that were not used in the operation but merely passed around.
  • Implement 2D table generator for org-mode

emacs lisp / common lisp

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
(defun cartesian-product-2 (l1 l2)
  (loop for x in l1
        nconc
        (loop for y in l2
              collect (list x y))))

(defun cartesian-product (&rest ls)
  (if (equal 1 (length ls))
      ls
    (mapcar '-flatten (-reduce 'cartesian-product-2 ls))))

(defalias '-cartesian-product 'cartesian-product)
(defalias '-cx 'cartesian-product)
1
(cartesian-product '(a b) '(1 2) '("h" "i"))
"((a 1 \"h\")
 (a 1 \"i\")
 (a 2 \"h\")
 (a 2 \"i\")
 (b 1 \"h\")
 (b 1 \"i\")
 (b 2 \"h\")
 (b 2 \"i\"))
"

Improvements

I want to flatten more intelligently.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
(defun uncdr (l)
  "Return car with cdr appended"
  (append (car l) (list (cdr l))))

(defun unsnd (l &optional depth)
  "Return car with cdr appended"

  (if (or (not depth)
          (< depth 1))
      (setq depth 1))

  (cond
   ((< 1 depth) (append (unsnd (car l) (- depth 1)) (list (second l))))
   (t (append (car l) (list (second l))))))
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
(defun cartesian-product (&rest ls)
  (let* ((len (length ls))
         (result (cond
                  ((not ls) nil)
                  ((equal 1 len) ls)
                  (t
                   (-reduce 'cartesian-product-2 ls)
                   ))))
    (if (< 2 len)
        (mapcar (lambda (l) (unsnd l (- len 2)))
                result)
      result)))

For example, I may be wanted to find the cartesian products of lists that may contain lists. I don’t want those sublists to take part in the cartesian product algorithm though. I want them to be treated the same as other data types. For that reason, I can’t use -flatten as it doesn’t discriminate between such lists and the lists we are targetting.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
(-cx '((";" 'ansi-zsh)
       ("'" 'eshell)
       ("\"" 'nw-term)
       ("s" 'eshell-sph)
       ("S" 'eshell-spv)
       ("g" 'split-window-below)
       ("G" 'split-window-right))
     '("w"
       "C-w"))

(-cx '((";" 'ansi-zsh)
       ("'" 'eshell)
       ("\"" 'nw-term)
       ("s" 'eshell-sph)
       ("S" 'eshell-spv)
       ("g" 'split-window-below)
       ("G" 'split-window-right))
     '("w"
       "C-w")
     '(my-mode-map
       global-map))

(-cx '("w"
       "C-w")
     '(my-mode-map
       global-map))

Defining keys using the Cartesian Product to generate code.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
(loop for d in
      (mapcar
       (lambda (l)
         `(define-key ,(third l) (kbd ,(concat "M-m " (second l) " " (car (car l)))) ,(second (car l))))
       (-cx '((";" 'ansi-zsh)
              ("'" 'eshell)
              ("\"" 'nw-term)
              ("s" 'eshell-sph)
              ("S" 'eshell-spv)
              ("g" 'split-window-below)
              ("G" 'split-window-right))
            '("w"
              "C-w")
            '(my-mode-map
              global-map)))
      do
      (ignore-errors
        (eval d)))

python

1
2
3
4
5
6
7
a = [["I"],["went","will go"],["to"],["the airport","the car","Jamaica"]]
from itertools import product

print([e for e in product(*a)])

for t in product(*a):
     print(" ".join(t))
[('I', 'went', 'to', 'the airport'), ('I', 'went', 'to', 'the car'), ('I', 'went', 'to', 'Jamaica'), ('I', 'will go', 'to', 'the airport'), ('I', 'will go', 'to', 'the car'), ('I', 'will go', 'to', 'Jamaica')]
I went to the airport
I went to the car
I went to Jamaica
I will go to the airport
I will go to the car
I will go to Jamaica

TODO recursion

haskell

1
2
3
4
5
:set -XFlexibleContexts

cartProd xs ys = [(x,y) | x <- xs, y <- ys]

cartProd [1 2 3] [11 12 13]

shell

Using brace expansion.

Sadly, this isn’t properly recursive when using nested braces.

1
printf "%s\n" {a,b,c}{{10,11,12},2,3}
a10
a11
a12
a2
a3
b10
b11
b12
b2
b3
c10
c11
c12
c2
c3
1
printf "%s\n" {a,b,c}{10,11,12,2,3}
a10
a11
a12
a2
a3
b10
b11
b12
b2
b3
c10
c11
c12
c2
c3