# Interleaving Sequences

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 , so the shortest code for each language wins.
• The only interleaving of no lists is the empty list. Does that mean that we have to output [[]] instead of [] when we are given no lists as input? Apr 17, 2018 at 10:17
• Also, will the lists have equal length? Apr 17, 2018 at 10:18
• I suppose it would be mathematically sane to return no lists as output if no lists are given as input. I will allow both. All the output lists will be equal length. Input lists may vary in length. Apr 17, 2018 at 15:25

# Python 2, 1039279 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.

• [x[0]] is x[:1]
– xnor
Apr 17, 2018 at 2:19
• @xnor: of course! thx! Apr 17, 2018 at 2:20

# Haskell, 8477 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! • 76 bytes by getting rid of some parentheses – user79465 Apr 17, 2018 at 1:07 # 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.  # 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]]  # Wolfram Language (Mathematica), 7675 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! # 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. • -3 by replacing sum(a,[]) with any(a). Apr 17, 2018 at 1:32 • @ChasBrown Thanks, I don't know Python that well. – Neil Apr 17, 2018 at 7:52 • Neil: Well enough, I think :). sum(a,[]) has nice use in some situations, though! Apr 17, 2018 at 8:08 # Haskell, 45 bytes f l=max[[]][h:y|h:t<-l,y<-f$t:filter(/=h:t)l]


Try it online!

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.

## 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]]:[[]]


# 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.

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!

• You should at least try to golf this code... Jun 28, 2018 at 21:40