Shuffles

Description of the problem

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.

An implementation in Common Lisp

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

SHUFFLES

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