Las secuencias intercaladas representan una fusión arbitraria de cierto número de secuencias.

Se puede hacer una secuencia intercalada agregando elementos a una lista uno por uno de un número de listas, eligiendo el siguiente elemento de alguna lista cada vez. Por lo tanto, una secuencia intercalada contendrá exactamente los mismos elementos de todas las listas combinadas, en un orden consistente con todas las listas.

La única intercalación de 1 lista es esa misma lista.

Desafío

Su desafío es crear una función / programa que tome un número arbitrario de secuencias y genere todos los posibles entrelazamientos de esas secuencias.

Ejemplos

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]

Reglas

Lagunas estándar prohibidas (duh)
La entrada puede tomarse en cualquier formato razonable, por ejemplo, una lista de listas, una lista vararg de listas, listas de parámetros, etc., siempre que no sea ambiguo dónde comienzan y terminan las listas.
La salida puede estar en cualquier formato razonable, siempre que esté claro dónde comienzan y terminan las listas. Las salidas válidas incluyen, pero no se limitan necesariamente a:
- stdout, con una lista por línea
- Una lista de listas
- Un iterador sobre listas (puede implementarse con un generador si su idioma los tiene)
El orden de los entrelazados cedidos no importa, sin embargo, no debería haber ningún entrelazado repetido.
Para simplificar la detección de repetición, puede suponer que todos los elementos en todas las secuencias de entrada son únicos.
Si no se proporcionan listas como entrada, tanto la lista vacía como ninguna salida son salidas válidas.
Los tipos de elementos en las secuencias son irrelevantes. (por ejemplo, todos pueden ser de un tipo o una mezcla de tipos, lo que sea más conveniente en su idioma)
Se debe garantizar que su programa / función termine en un tiempo finito.
Este es el código de golf , por lo que gana el código más corto para cada idioma.

code-golf sequence Carne de res
fuente

La única intercalación de ninguna lista es la lista vacía. ¿Significa eso que tenemos que generar en [[]]lugar de []cuando no se nos dan listas como entrada?

Erik the Outgolfer

Además, ¿tendrán las listas la misma longitud?

Erik the Outgolfer

Supongo que sería matemáticamente sensato no devolver listas como salida si no se dan listas como entrada. Permitiré ambos. Todas las listas de salida tendrán la misma longitud. Las listas de entrada pueden variar en longitud.

Beefster

6

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]

¡Gracias a @Lynn por 7 bytes y a @ user9549915 por un byte!

Pruébalo en línea!

Angs
fuente

76 bytes al deshacerse de algunos paréntesis

user9549915

5

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

Pruébalo en línea!

O:

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)

Pruébalo en línea!

-1 mediante la sustitución [x[0]]con x[:1]como por xnor

-13 bytes ~~robando descaradamente~~ expandiéndose según [b[b==x:]for b in A]lo sugerido por la respuesta de Neil en lugar de un enumerateenfoque más largo .

Toma una lista de listas Acomo entrada. Si todos los elementos de Aestán vacíos, la lista evaluada en el ifestará vacía, por lo que hemos llegado al final de la recursión y podemos print. De lo contrario, tenemos una lista de uno o más None; y recurrimos

Chas Brown
fuente

[x[0]]esx[:1]

xnor

@xnor: por supuesto! ¡Gracias!

Chas Brown

4

Jalea , 11 bytes

FŒ!fÐ€⁼ṛɗÐf

Pruébalo en línea!

Cómo 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.

Dennis
fuente

3

Ruby, 66 bytes

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

Si no hay secuencias no vacías, devuelva una secuencia vacía. De lo contrario, para cada secuencia no vacía, repita con el primer elemento eliminado y luego agréguelo al comienzo de cada resultado. La implementación utiliza el supuesto de que los elementos están garantizados para ser globalmente únicos, de lo contrario a-[b]podría eliminar más de 1 secuencia de la llamada recursiva. Aunque reflexionando, tal vez ese sería realmente el comportamiento correcto para evitar resultados duplicados.

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

histocrat
fuente

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/@#)]&

Pruébalo en línea!

Enfoque ingenuo: encuentre todas las permutaciones que son entrelazados de la entrada.

Explicación

Permutations[Join@@#]

Aplane <input>y encuentre todas sus permutaciones.

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

Encuentra todos los elementos de xmanera que ...

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

Reemplace todos los elementos en profundidad-2 de <input>con su respectiva posición en x.

And@@OrderedQ/@ ...

Compruebe si todas las listas de profundidad 1 están ordenadas (es decir, en orden creciente).

Implementación real de intercalado, 117 bytes

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

Pruébalo en línea!

JungHwan Min
fuente

2

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

Pruébalo en línea! Puerto de mi respuesta de JavaScript. Editar: Guardado 3 bytes gracias a @ChasBrown.

Neil
fuente

-3 reemplazando sum(a,[])con any(a).

Chas Brown

@ChasBrown Gracias, no conozco Python tan bien.

Neil

Neil: Bueno, creo que :). sum(a,[])Sin embargo, tiene un buen uso en algunas situaciones.

Chas Brown

2

Haskell , 45 bytes

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

Pruébalo en línea!

Adaptado de la respuesta Python de Chas Brown .

El max[[]]es un truco para dar un caso base de [[]]cuando la entrada solo contiene []elementos. En ese caso, la lista utilizada para vacío, recurrente está vacía, y max[[]][]da [[]].

Al recurrir, en lugar de descartar selectivamente el primer elemento de la lista elegida h:t, creamos una nueva lista tal frente y h:tfiltrada.

xnor
fuente

0

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

Neil
fuente

0

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.

Toma entrada como una matriz de matrices. -Qhace que la salida conserve la notación de matriz.

Pruébalo aquí

Liendre
fuente

0

Scala: (no pretende ser mínimo, más un recurso de referencia 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))))
}

Pruébalo en línea!

satyagraha
fuente

1

Al menos deberías intentar jugar este código ...

Timtech

Secuencias de entrelazado

Desafío

Ejemplos

Reglas

Respuestas:

Haskell , 84 77 76 bytes

Python 2 , 103 92 79 78 bytes

Python 3 , 73 bytes

Jalea , 11 bytes

Cómo funciona

Ruby, 66 bytes

Wolfram Language (Mathematica) , 76 75 71 bytes

Explicación

Implementación real de intercalado, 117 bytes

Python 2 , 87 84 bytes

Haskell , 45 bytes

JavaScript (Firefox 30-57), 92 bytes

Japt `-Q` , 14 bytes

Secuencias de entrelazado

Desafío

Ejemplos

Reglas

Respuestas:

Haskell , 84 77 76 bytes

Python 2 , 103 92 79 78 bytes

Python 3 , 73 bytes

Jalea , 11 bytes

Cómo funciona

Ruby, 66 bytes

Wolfram Language (Mathematica) , 76 75 71 bytes

Explicación

Implementación real de intercalado, 117 bytes

Python 2 , 87 84 bytes

Haskell , 45 bytes

JavaScript (Firefox 30-57), 92 bytes

Japt -Q , 14 bytes

Japt `-Q` , 14 bytes