Given two sequences of integers \(x_1,...,x_n\) and \(y_1,...,y_m\), a shuffle is a new sequence of length \(n+m\) where we use all of \(x_i\)’s and \(y_j\)’s exactly once. Moreover, each \(x_i\) and \(y_j\) appear in their original order. For example if
(0 2 4)
(1 3 5 7)are two such sequences
(1 0 3 5 2 7 4)is a shuffle while
(1 3 0 2 7 4 5)is not because 7 appears before 5.
Today, I’ll write a lisp function which takes two ordered lists and returns all of their shuffles.
The following is a recursive implementation.
(defun shuffles (xs ys &optional (acc (list nil)))
(labels ((insert (a as) (mapcar (lambda (x) (cons a x)) as))
(paste (as bs) (mapcar (lambda (b) (append (reverse b) as)) bs)))
(cond ((null xs) (paste ys acc))
((null ys) (paste xs acc))
(t (append (shuffles (cdr xs) ys (insert (car xs) acc))
(shuffles xs (cdr ys) (insert (car ys) acc)))))))
SHUFFLESIf you look at the code you will see that it has exponential complexity. Oh well… Here is a test
(shuffles '(0 2 4) '(1 3 5 7))
((0 2 4 1 3 5 7) (0 2 1 4 3 5 7) (0 2 1 3 4 5 7) (0 2 1 3 5 4 7)
(0 2 1 3 5 7 4) (0 1 2 4 3 5 7) (0 1 2 3 4 5 7) (0 1 2 3 5 4 7)
(0 1 2 3 5 7 4) (0 1 3 2 4 5 7) (0 1 3 2 5 4 7) (0 1 3 2 5 7 4)
(0 1 3 5 2 4 7) (0 1 3 5 2 7 4) (0 1 3 5 7 2 4) (1 0 2 4 3 5 7)
(1 0 2 3 4 5 7) (1 0 2 3 5 4 7) (1 0 2 3 5 7 4) (1 0 3 2 4 5 7)
(1 0 3 2 5 4 7) (1 0 3 2 5 7 4) (1 0 3 5 2 4 7) (1 0 3 5 2 7 4)
(1 0 3 5 7 2 4) (1 3 0 2 4 5 7) (1 3 0 2 5 4 7) (1 3 0 2 5 7 4)
(1 3 0 5 2 4 7) (1 3 0 5 2 7 4) (1 3 0 5 7 2 4) (1 3 5 0 2 4 7)
(1 3 5 0 2 7 4) (1 3 5 0 7 2 4) (1 3 5 7 0 2 4))