Przeplecione sekwencje reprezentują dowolne łączenie pewnej liczby sekwencji.

Przeplecioną sekwencję można utworzyć, dodając elementy do listy jeden po drugim z pewnej liczby list, wybierając za każdym razem następny element z jakiejś listy. Dlatego sekwencja przeplatana będzie zawierać dokładnie te same elementy wszystkich list razem, w kolejności zgodnej ze wszystkimi listami.

Jedynym przeplotem 1 listy jest ta sama lista.

Wyzwanie

Wyzwanie polega na utworzeniu funkcji / programu, który pobierze dowolną liczbę sekwencji i wyświetli wszystkie możliwe przeplatania tych sekwencji.

Przykłady

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]

Zasady

• Standardowe luki zabronione (duh)
• Dane wejściowe można przyjmować w dowolnym rozsądnym formacie, np. Lista list, lista vararg list, lista parametrów itp., O ile nie jest jednoznaczne, gdzie listy zaczynają się i kończą.
• Dane wyjściowe mogą być w dowolnym rozsądnym formacie, o ile jest jasne, gdzie listy zaczynają się i kończą. Prawidłowe dane wyjściowe obejmują między innymi:
  • standardowe, z jedną listą w wierszu
  • Lista list
  • Iterator list (może być zaimplementowany z generatorem, jeśli Twój język je posiada)
• Kolejność uzyskanych przeplotów nie ma znaczenia, jednak nie powinno być żadnych powtarzających się przeplotów.
• Aby uprościć wykrywanie powtarzania, możesz założyć, że wszystkie elementy we wszystkich sekwencjach wejściowych są unikalne.
• Jeśli jako dane wejściowe nie podano żadnych list, zarówno pusta lista, jak i brak danych wyjściowych są prawidłowymi danymi wyjściowymi.
• Rodzaje elementów w sekwencji nie mają znaczenia. (np. wszystkie mogą być jednym typem lub mieszanką typów, w zależności od tego, który z nich jest wygodniejszy w Twoim języku)
• Twój program / funkcja musi mieć zagwarantowane zakończenie w określonym czasie.
• To jest golf golfowy , więc wygrywa najkrótszy kod dla każdego języka.

Haskell , 84 77 76 bajtów

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

Dzięki @Lynn za 7 bajtów i @ user9549915 za bajt!

Wypróbuj online!

Python 2 , 103 92 79 78 bajtów

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

Wypróbuj online!

Lub:

Python 3 , 73 bajty

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

Wypróbuj online!

-1 przez zastąpienie zgodnie [x[0]]z xnorx[:1]

-13 bajtów przez bezwstydne kradzież rozwijania, [b[b==x:]for b in A]jak sugeruje odpowiedź Neila, zamiast dłuższego enumeratepodejścia.

Pobiera na Awejściu listę list . Jeśli wszystkie elementy Asą puste, lista oceniona w ifbędzie pusta, więc doszliśmy do końca rekurencji i możemy print. W przeciwnym razie mamy listę jednego lub więcej None; i wracamy.

Galaretka , 11 bajtów

FŒ!fЀ⁼ṛɗÐf

Wypróbuj online!

Jak to działa

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.

Rubin, 66 bajtów

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

Jeśli nie ma niepustych sekwencji, zwróć pustą sekwencję. W przeciwnym razie dla każdej niepustej sekwencji powtórz z pierwszym elementem usuniętym, a następnie dodaj go na początku każdego wyniku. W implementacji przyjęto założenie, że elementy są globalnie unikalne, w przeciwnym razie a-[b]mogłoby potencjalnie usunąć więcej niż 1 sekwencję z wywołania rekurencyjnego. Mimo refleksji, być może byłoby to właściwe zachowanie, aby uniknąć powielania wyników.

Przykład 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 bajtów

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

Wypróbuj online!

Naiwne podejście: znajdź wszystkie permutacje, które są przeplotem danych wejściowych.

Wyjaśnienie

Permutations[Join@@#]

Spłaszcz <input>i znajdź wszystkie jego permutacje.

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

Znajdź wszystkie elementy x, które ...

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

Wymień wszystkie elementy na głębokości-2 <input>z odpowiednią pozycją w x.

And@@OrderedQ/@ ...

Sprawdź, czy wszystkie listy głębokości-1 są uporządkowane (tzn. W porządku rosnącym).

Rzeczywista implementacja przeplatania, 117 bajtów

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

Wypróbuj online!

Python 2 , 87 84 bajtów

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

Wypróbuj online! Port mojej odpowiedzi JavaScript. Edycja: Zapisano 3 bajty dzięki @ChasBrown.

Haskell , 45 bajtów

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

Wypróbuj online!

Na podstawie odpowiedzi Pytona Chasa Browna .

max[[]]Trik dać bazowego przypadku [[]]gdy wejście zawiera tylko []elementy. W takim przypadku lista używana do pustego, cyklicznego jest pusta i max[[]][]daje [[]].

Podczas rekurencji, zamiast selektywnego upuszczania pierwszego elementu wybranej listy h:t, tworzymy nową listę z tprzodu i h:todfiltrowujemy.

JavaScript (Firefox 30-57), 92 bajty

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 bajtów

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.

Pobiera dane wejściowe jako tablicę tablic. -Qsprawia, że ​​dane wyjściowe zachowują notację tablicową.

Wypróbuj tutaj.

Scala: (nie ma być minimalny, bardziej przejrzysty zasób referencyjny)

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

Wypróbuj online!