Interleaving Sequences

Question

Interleaved sequences represent an arbitrary merging of some number of sequences.

An interleaved sequence can be made by appending elements to a list one by one from some number of lists, choosing the next element from some list each time. Therefore, an interleaved sequence will contain exactly the same elements of all the lists combined, in an order consistent with all lists.

The only interleaving of 1 list is that same list.

Challenge

Your challenge is to create a function/program that takes an arbitrary number of sequences and outputs all possible interleavings of those sequences.

Examples

Input: [1, 2], [3, 4]
Output:
    [1, 2, 3, 4]
    [1, 3, 2, 4]
    [1, 3, 4, 2] 
    [3, 1, 2, 4]
    [3, 1, 4, 2]
    [3, 4, 1, 2]

Input: [1, 2, 3, 4, 5]
Output:
    [1, 2, 3, 4, 5]

Input: []
Output:
    []

Input: <nothing>
Output:
    []

(also acceptable)
Input: <nothing>
Output: <nothing>

Input: [1, 2, 3], [4, 5]
Output:
    [1, 2, 3, 4, 5]
    [1, 2, 4, 3, 5]
    [1, 2, 4, 5, 3]
    [1, 4, 2, 3, 5]
    [1, 4, 2, 5, 3]
    [1, 4, 5, 2, 3]
    [4, 1, 2, 3, 5]
    [4, 1, 2, 5, 3]
    [4, 1, 5, 2, 3]
    [4, 5, 1, 2, 3]

Input: [1, 2], [3, 4], [5, 6]
Output:
    [1, 2, 3, 4, 5, 6]
    [1, 2, 3, 5, 4, 6]
    [1, 2, 3, 5, 6, 4]
    [1, 2, 5, 3, 4, 6]
    [1, 2, 5, 3, 6, 4]
    [1, 2, 5, 6, 3, 4]
    [1, 3, 2, 4, 5, 6]
    [1, 3, 2, 5, 4, 6]
    [1, 3, 2, 5, 6, 4]
    [1, 3, 4, 2, 5, 6]
    [1, 3, 4, 5, 2, 6]
    [1, 3, 4, 5, 6, 2]
    [1, 3, 5, 2, 4, 6]
    [1, 3, 5, 2, 6, 4]
    [1, 3, 5, 4, 2, 6]
    [1, 3, 5, 4, 6, 2]
    [1, 3, 5, 6, 2, 4]
    [1, 3, 5, 6, 4, 2]
    [1, 5, 2, 3, 4, 6]
    [1, 5, 2, 3, 6, 4]
    [1, 5, 2, 6, 3, 4]
    [1, 5, 3, 2, 4, 6]
    [1, 5, 3, 2, 6, 4]
    [1, 5, 3, 4, 2, 6]
    [1, 5, 3, 4, 6, 2]
    [1, 5, 3, 6, 2, 4]
    [1, 5, 3, 6, 4, 2]
    [1, 5, 6, 2, 3, 4]
    [1, 5, 6, 3, 2, 4]
    [1, 5, 6, 3, 4, 2]
    [3, 1, 2, 4, 5, 6]
    [3, 1, 2, 5, 4, 6]
    [3, 1, 2, 5, 6, 4]
    [3, 1, 4, 2, 5, 6]
    [3, 1, 4, 5, 2, 6]
    [3, 1, 4, 5, 6, 2]
    [3, 1, 5, 2, 4, 6]
    [3, 1, 5, 2, 6, 4]
    [3, 1, 5, 4, 2, 6]
    [3, 1, 5, 4, 6, 2]
    [3, 1, 5, 6, 2, 4]
    [3, 1, 5, 6, 4, 2]
    [3, 4, 1, 2, 5, 6]
    [3, 4, 1, 5, 2, 6]
    [3, 4, 1, 5, 6, 2]
    [3, 4, 5, 1, 2, 6]
    [3, 4, 5, 1, 6, 2]
    [3, 4, 5, 6, 1, 2]
    [3, 5, 1, 2, 4, 6]
    [3, 5, 1, 2, 6, 4]
    [3, 5, 1, 4, 2, 6]
    [3, 5, 1, 4, 6, 2]
    [3, 5, 1, 6, 2, 4]
    [3, 5, 1, 6, 4, 2]
    [3, 5, 4, 1, 2, 6]
    [3, 5, 4, 1, 6, 2]
    [3, 5, 4, 6, 1, 2]
    [3, 5, 6, 1, 2, 4]
    [3, 5, 6, 1, 4, 2]
    [3, 5, 6, 4, 1, 2]
    [5, 1, 2, 3, 4, 6]
    [5, 1, 2, 3, 6, 4]
    [5, 1, 2, 6, 3, 4]
    [5, 1, 3, 2, 4, 6]
    [5, 1, 3, 2, 6, 4]
    [5, 1, 3, 4, 2, 6]
    [5, 1, 3, 4, 6, 2]
    [5, 1, 3, 6, 2, 4]
    [5, 1, 3, 6, 4, 2]
    [5, 1, 6, 2, 3, 4]
    [5, 1, 6, 3, 2, 4]
    [5, 1, 6, 3, 4, 2]
    [5, 3, 1, 2, 4, 6]
    [5, 3, 1, 2, 6, 4]
    [5, 3, 1, 4, 2, 6]
    [5, 3, 1, 4, 6, 2]
    [5, 3, 1, 6, 2, 4]
    [5, 3, 1, 6, 4, 2]
    [5, 3, 4, 1, 2, 6]
    [5, 3, 4, 1, 6, 2]
    [5, 3, 4, 6, 1, 2]
    [5, 3, 6, 1, 2, 4]
    [5, 3, 6, 1, 4, 2]
    [5, 3, 6, 4, 1, 2]
    [5, 6, 1, 2, 3, 4]
    [5, 6, 1, 3, 2, 4]
    [5, 6, 1, 3, 4, 2]
    [5, 6, 3, 1, 2, 4]
    [5, 6, 3, 1, 4, 2]
    [5, 6, 3, 4, 1, 2]

Rules

• Standard loopholes forbidden (duh)
• Input may be taken in any reasonable format, e.g. a list of lists, vararg list of lists, parameter lists, etc... as long as it is unambiguous where lists begin and end.
• Output may be in any reasonable format, so long as it is clear where lists begin and end. Valid outputs include, but are not necessarily limited to:
  • stdout, with one list per line
  • A list of lists
  • An iterator over lists (can be implemented with a generator if your language has them)
• The order of the yielded interleavings does not matter, however, there should not be any repeated interleavings.
• To simplify repeat detection, you may assume that all elements across all input sequences are unique.
• If given no lists as input, both the empty list and no output are valid outputs.
• Types of the elements in the sequences is irrelevant. (e.g. they could all be one type or a mishmash of types, whichever is more convenient in your language)
• Your program/function must be guaranteed to terminate in a finite amount of time.
• This is code-golf, so the shortest code for each language wins.

Answer 1

Python 2, 103 92 79 78 bytes

def f(A,c=[]):
 if not[f([b[b==x:]for b in A],c+x[:1])for x in A if x]:print c

Try it online!

Or:

Python 3, 73 bytes

def f(A,c=[]):[f([b[b==x:]for b in A],c+x[:1])for x in A if x]or print(c)

Try it online!

-1 by replacing [x[0]] with x[:1] as per xnor

-13 bytes by shamelessly stealing expanding upon [b[b==x:]for b in A] as suggested by Neil's answer instead of longer enumerate approach.

Takes a list of lists A as input. If all elements of A are empty, then the list evaluated in the if will be empty, so we have reached the end of the recursion and can print. Otherwise, we have a list of one or more None's; and we recurse.

Answer 2

Haskell, 84 77 76 bytes

foldl((.(!)).(>>=))[[]]
a#b=(b:)<$>a
x@(a:c)!y@(b:d)=x!d#b++c!y#a
a!b=[a++b]

Thanks to @Lynn for 7 bytes and @user9549915 for a byte!

Try it online!

Answer 3

Jelly, 11 bytes

FŒ!fЀ⁼ṛɗÐf

Try it online!

How it works

FŒ!fЀ⁼ṛɗÐf  Main link. Argument: A (array of arrays)

F            Flatten A.
 Œ!          Take all permutations.
        ɗÐf  Filter by the chain to the left, keeping only permutations for which
             it returns a truthy value.
   fЀ         Intersect the permutation with each array in A.
      ⁼ṛ       Test if the result is equal to A.

Answer 4

Ruby, 66 bytes

f=->a,*p{(a-=[[]])[0]?a.flat_map{|b|h,*t=b;f[a-[b]+[t],*p,h]}:[p]}

If there are no non-empty sequences, return an empty sequence. Otherwise, for each non-empty sequence, recurse with the first element removed then add it onto the beginning of each result. The implementation uses the assumption that elements are guaranteed to be globally unique, otherwise a-[b] could potentially remove more than 1 sequence from the recursive call. Although on reflection, maybe that'd actually be the right behavior to avoid duplicate output.

Example IO:

f[[[1,2],[3,4]]] => [[1, 3, 2, 4], [1, 3, 4, 2], [1, 2, 3, 4], [3, 1, 4, 2], [3, 1, 2, 4], [3, 4, 1, 2]]

Answer 5

Wolfram Language (Mathematica), 76 75 71 bytes

Cases[Permutations[Join@@#],x_/;And@@OrderedQ/@(x~Position~#&/@#&/@#)]&
(* or *)
Cases[Join/*Permutations@@#,x_/;And@@(x~Position~#&/@#&/*OrderedQ/@#)]&

Try it online!

Naive approach: find all permutations that are interleavings of the input.

Explanation

Permutations[Join@@#]

Flatten <input> and find all of its permutations.

Cases[ ... ,x_/; ...]

Find all elements x such that...

(x~Position~#&/@#&/@#)

Replace all of the items in depth-2 of <input> with their respective position in x.

And@@OrderedQ/@ ...

Check whether all depth-1 lists are ordered (i.e. in increasing order).

Actual implementation of interleaving, 117 bytes

Cases[{}~(f=ReplaceList[#2,{{a___,{b_,c___},d___}/;b>0:>#~Join~{b}~f~{a,{c},d},_:>#}]&)~#,{___},{Tr[1^(Join@@#)]+1}]&

Try it online!

Answer 6

Python 2, 87 84 bytes

f=lambda a:any(a)and[b[:1]+c for b in a if b for c in f([c[c==b:]for c in a])]or[[]]

Try it online! Port of my JavaScript answer. Edit: Saved 3 bytes thanks to @ChasBrown.

Answer 7

Haskell, 45 bytes

f l=max[[]][h:y|h:t<-l,y<-f$t:filter(/=h:t)l]

Try it online!

Adapted from Chas Brown's Python answer.

The max[[]] is a trick to give a base case of [[]] when the input only contains [] elements. In that case, the list used for empty, recursing is empty, and max[[]][] gives [[]].

When recursing, rather than selectively dropping the first element of the chosen list h:t, we make a new list with t at the front and h:t filtered out.

Answer 8

JavaScript (Firefox 30-57), 92 bytes

f=a=>a.some(b=>b+b)?[for(b of a)if(b+b)for(c of f(a.map(c=>c.slice(c==b))))[b[0],...c]]:[[]]

Answer 9

Japt -Q, 14 bytes

c á f@e_XfZ eZ
c              // Flatten the input into a single array
  á            // and find all permutations.
    f          // Then filter the results for items
     @e_       // where for each original input
        XfZ eZ // the ordering of the items is unchanged.

Takes input as an array of arrays. -Q makes the output preserve the array notation.

Try it here.

Answer 10

Scala: (not intended to be minimal, more a clear reference resource)

object Interleave {

  private def interleavePair[A](x: Seq[A], y: Seq[A]): Seq[Seq[A]] =
    (x, y) match {
      case (a +: c, b +: d) =>
        interleavePair(x, d).map(b +: _) ++ interleavePair(c, y).map(a +: _)
      case _ => Seq(x ++ y)
    }

  def interleave[A](ssa: Seq[Seq[A]]): Seq[Seq[A]] =
    ssa.foldLeft[Seq[Seq[A]]](Seq(Seq.empty)) {
      case (sssat, sa) => sssat.flatMap(interleavePair(sa, _))
    }
}

object Main extends App {

  import Interleave._

  println(interleave(Seq()))
  println(interleave(Seq(Seq(1, 2), Seq(3, 4))))
}

Try it online!