Generating all tuples (Lisp)

From LiteratePrograms

Jump to: navigation, search
Other implementations: Haskell | Lisp | Perl | Python | Ruby

This is a simple example of the tuples generation algorithm, written in Common Lisp.

see The Art of Computer Programming (TAOCP) Volume 4 Fascicle 2, Generating All Tuples and Permutations (2005), ISBN 0-201-85393-0

Algorithm M

The generation function is genTuplesM as below:

  • Input parameter: we list the limits on each bit into a list as an input
  • Output: generating all possible tuples
(defun gen-tuples-m (lst)
  (reduce (lambda (b rest)
            (loop for xs in rest
                  append (loop for i from 1 to b
                               collecting (cons i xs))))
          :from-end t
          :initial-value '(())))
(gen-tuples-m '(3 5 3 2))


Just load the file genTuplesM.lsp in Common Lisp, execute it and you will get the result.

Download code
Personal tools