Sequências intercaladas representam uma fusão arbitrária de algum número de sequências.

Uma sequência intercalada pode ser feita anexando elementos a uma lista, um a um, a partir de algum número de listas, escolhendo o próximo elemento de uma lista a cada vez. Portanto, uma sequência intercalada conterá exatamente os mesmos elementos de todas as listas combinadas, em uma ordem consistente com todas as listas.

A única intercalação de 1 lista é a mesma lista.

Desafio

Seu desafio é criar uma função / programa que pegue um número arbitrário de seqüências e produza todas as intercalações possíveis dessas seqüências.

Exemplos

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]

Regras

• Brechas padrão proibidas (duh)
• As entradas podem ser obtidas em qualquer formato razoável, por exemplo, uma lista de listas, vararg lista de listas, listas de parâmetros, etc ... desde que seja inequívoco onde as listas começam e terminam.
• A saída pode estar em qualquer formato razoável, desde que fique claro onde as listas começam e terminam. Saídas válidas incluem, mas não estão necessariamente limitadas a:
  • stdout, com uma lista por linha
  • Uma lista de listas
  • Um iterador sobre listas (pode ser implementado com um gerador se o seu idioma as possuir)
• A ordem das intercalações produzidas não importa, no entanto, não deve haver intercalações repetidas.
• Para simplificar a detecção de repetição, você pode assumir que todos os elementos em todas as seqüências de entrada são únicos.
• Se nenhuma lista for fornecida como entrada, a lista vazia e nenhuma saída serão saídas válidas.
• Os tipos dos elementos nas sequências são irrelevantes. (por exemplo, todos eles podem ser de um tipo ou uma mistura de tipos, o que for mais conveniente no seu idioma)
• Seu programa / função deve ter a garantia de término em um período finito de tempo.
• Isso é código-golfe , portanto o código mais curto para cada idioma vence.

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]

Obrigado a @Lynn por 7 bytes e a @ user9549915 por um byte!

Experimente online!

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

Experimente online!

Ou:

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)

Experimente online!

-1 substituindo [x[0]]por x[:1]conforme xnor

-13 bytes, roubando descaradamente a expansão, [b[b==x:]for b in A]conforme sugerido pela resposta de Neil, em vez de uma enumerateabordagem mais longa .

Leva uma lista de listas Acomo entrada. Se todos os elementos de Aestiverem vazios, a lista avaliada em ifestará vazia; portanto, chegamos ao final da recursão e podemos print. Caso contrário, temos uma lista de um ou mais None's; e nós recomendamos.

Gelatina , 11 bytes

FŒ!fЀ⁼ṛɗÐf

Experimente online!

Como funciona

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]}

Se não houver seqüências não vazias, retorne uma sequência vazia. Caso contrário, para cada sequência não vazia, recorra com o primeiro elemento removido e adicione-o no início de cada resultado. A implementação usa a suposição de que os elementos têm garantia de serem exclusivos globalmente; caso contrário, a-[b]poderiam remover mais de uma sequência da chamada recursiva. Embora refletindo, talvez esse seja realmente o comportamento certo para evitar saída duplicada.

Exemplo 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) , 76 75 71 bytes

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

Experimente online!

Abordagem ingênua: encontre todas as permutações que são intercalações da entrada.

Explicação

Permutations[Join@@#]

Achate <input>e encontre todas as suas permutações.

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

Encontre todos os elementos de xmodo que ...

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

Substitua todos os itens na profundidade 2 de <input>com sua respectiva posição x.

And@@OrderedQ/@ ...

Verifique se todas as listas de profundidade 1 estão ordenadas (ou seja, em ordem crescente).

Implementação real da intercalação, 117 bytes

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

Experimente 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[[]]

Experimente online! Porta da minha resposta JavaScript. Editar: salvou 3 bytes graças a @ChasBrown.

Haskell , 45 bytes

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

Experimente online!

Adaptado da resposta Python de Chas Brown .

A max[[]]é um truque para dar uma base de caso de [[]]quando a entrada contém apenas []elementos. Nesse caso, a lista usada para vazio e recorrente está vazia e max[[]][]fornece [[]].

Ao repetir, em vez de eliminar seletivamente o primeiro elemento da lista escolhida h:t, fazemos uma nova lista tna frente e h:tfiltramos.

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

Japonês -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.

Recebe a entrada como uma matriz de matrizes. -Qfaz com que a saída preserve a notação da matriz.

Experimente aqui.

Scala: (não pretende ser mínimo, mais um recurso de referência claro)

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

Experimente online!