Les séquences entrelacées représentent une fusion arbitraire d'un certain nombre de séquences.

Une séquence entrelacée peut être effectuée en ajoutant des éléments à une liste un par un parmi un certain nombre de listes, en choisissant à chaque fois l'élément suivant dans une liste. Par conséquent, une séquence entrelacée contiendra exactement les mêmes éléments de toutes les listes combinées, dans un ordre cohérent avec toutes les listes.

Le seul entrelacement de 1 liste est cette même liste.

Défi

Votre défi est de créer une fonction / programme qui prend un nombre arbitraire de séquences et génère tous les entrelacements possibles de ces séquences.

Exemples

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]

Règles

• Failles standard interdites (duh)
• L'entrée peut être prise dans n'importe quel format raisonnable, par exemple une liste de listes, une liste vararg de listes, des listes de paramètres, etc ... tant qu'il n'est pas ambigu où les listes commencent et se terminent.
• La sortie peut être dans n'importe quel format raisonnable, tant qu'il est clair où les listes commencent et se terminent. Les sorties valides incluent, mais ne sont pas nécessairement limitées à:
  • stdout, avec une liste par ligne
  • Une liste de listes
  • Un itérateur sur les listes (peut être implémenté avec un générateur si votre langue en possède)
• L'ordre des entrelacements produits n'a pas d'importance, cependant, il ne devrait pas y avoir d'entrelacements répétés.
• Pour simplifier la détection de répétition, vous pouvez supposer que tous les éléments de toutes les séquences d'entrée sont uniques.
• Si aucune liste d'entrée n'est donnée, la liste vide et aucune sortie sont des sorties valides.
• Les types d'éléments dans les séquences ne sont pas pertinents. (par exemple, ils pourraient tous être d'un type ou d'un méli-mélo de types, selon ce qui est plus pratique dans votre langue)
• Votre programme / fonction doit être garanti de se terminer dans un laps de temps fini.
• C'est le code-golf , donc le code le plus court pour chaque langue l'emporte.

Haskell , 84 77 76 octets

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

Merci à @Lynn pour 7 octets et @ user9549915 pour un octet!

Essayez-le en ligne!

Python 2 , 103 92 79 78 octets

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

Essayez-le en ligne!

Ou:

Python 3 , 73 octets

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

Essayez-le en ligne!

-1 en remplaçant [x[0]]par x[:1]selon xnor

-13 octets en volant sans vergogne en se développant [b[b==x:]for b in A]comme suggéré par la réponse de Neil au lieu d'une enumerateapproche plus longue .

Prend une liste de listes Aen entrée. Si tous les éléments de Asont vides, alors la liste évaluée dans le ifsera vide, nous avons donc atteint la fin de la récursivité et le pouvons print. Sinon, nous avons une liste d'un ou plusieurs None; et nous recurse.

Gelée , 11 octets

FŒ!fЀ⁼ṛɗÐf

Essayez-le en ligne!

Comment ça fonctionne

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.

Rubis, 66 octets

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

S'il n'y a pas de séquences non vides, renvoyez une séquence vide. Sinon, pour chaque séquence non vide, répétez avec le premier élément supprimé puis ajoutez-le au début de chaque résultat. L'implémentation utilise l'hypothèse que les éléments sont garantis comme étant globalement uniques, sinon ils a-[b]pourraient potentiellement supprimer plus d'une séquence de l'appel récursif. Bien qu'à la réflexion, ce serait peut-être le bon comportement pour éviter la sortie en double.

Exemple 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 octets

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

Essayez-le en ligne!

Approche naïve: trouvez toutes les permutations qui sont des entrelacements de l'entrée.

Explication

Permutations[Join@@#]

Aplatissez <input>et retrouvez toutes ses permutations.

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

Trouvez tous les éléments xtels que ...

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

Remplacez tous les éléments en profondeur 2 <input>par leur position respective dans x.

And@@OrderedQ/@ ...

Vérifiez si toutes les listes de profondeur 1 sont ordonnées (c.-à-d. Dans un ordre croissant).

Implémentation réelle de l'entrelacement, 117 octets

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

Essayez-le en ligne!

Python 2 , 87 84 octets

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

Essayez-le en ligne! Port de ma réponse JavaScript. Edit: enregistré 3 octets grâce à @ChasBrown.

Haskell , 45 octets

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

Essayez-le en ligne!

Adapté de la réponse Python de Chas Brown .

C'est max[[]]une astuce pour donner un cas de base [[]]lorsque l'entrée ne contient que des []éléments. Dans ce cas, la liste utilisée pour vide, récursif est vide, et max[[]][]donne [[]].

Lors de la récurrence, plutôt que de supprimer sélectivement le premier élément de la liste choisie h:t, nous créons une nouvelle liste avec tau début et h:tfiltrée.

JavaScript (Firefox 30-57), 92 octets

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 octets

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.

Prend l'entrée comme un tableau de tableaux. -Qfait que la sortie conserve la notation du tableau.

Essayez-le ici.

Scala: (pas destiné à être minimal, plus une ressource de référence claire)

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

Essayez-le en ligne!