Urutan interleaved merupakan penggabungan sewenang-wenang dari sejumlah urutan.

Urutan yang saling terkait dapat dibuat dengan menambahkan elemen ke daftar satu per satu dari beberapa daftar, memilih elemen berikutnya dari beberapa daftar setiap kali. Oleh karena itu, urutan yang disisipkan akan berisi elemen yang persis sama dari semua daftar yang digabungkan, dalam urutan yang konsisten dengan semua daftar.

Satu-satunya interleaving dari 1 daftar adalah daftar yang sama.

Tantangan

Tantangan Anda adalah untuk membuat fungsi / program yang mengambil sejumlah urutan dan hasil sewenang-wenang semua interleavings yang mungkin dari urutan tersebut.

Contohnya

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]

Aturan

• Celah standar terlarang
• Input dapat diambil dalam format apa pun yang masuk akal, misalnya daftar daftar, daftar daftar vararg, daftar parameter, dll ... selama tidak jelas di mana daftar mulai dan berakhir.
• Output mungkin dalam format yang masuk akal, selama jelas di mana daftar mulai dan berakhir. Output yang valid termasuk, tetapi tidak terbatas pada:
  • stdout, dengan satu daftar per baris
  • Daftar daftar
  • Sebuah daftar iterator over (dapat diimplementasikan dengan generator jika bahasa Anda memilikinya)
• Urutan interleavings yang dihasilkan tidak masalah, namun, seharusnya tidak ada interleavings berulang.
• Untuk menyederhanakan deteksi berulang, Anda dapat mengasumsikan bahwa semua elemen di semua urutan input adalah unik.
• Jika tidak diberi daftar sebagai input, daftar kosong dan tidak ada output adalah output yang valid.
• Jenis elemen dalam sekuens tidak relevan. (mis. mereka semua bisa menjadi satu jenis atau jenis kesalahan, yang lebih nyaman dalam bahasa Anda)
• Program / fungsi Anda harus dijamin akan berakhir dalam waktu yang terbatas.
• Ini adalah kode-golf , jadi kode terpendek untuk setiap bahasa menang.

Haskell , 84 77 76 byte

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

Terima kasih kepada @Lynn selama 7 byte dan @ user9549915 untuk satu byte!

Cobalah online!

Python 2 , 103 92 79 78 byte

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

Cobalah online!

Atau:

Python 3 , 73 byte

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

Cobalah online!

-1 dengan mengganti [x[0]]dengan x[:1]sesuai xnor

-13 byte dengan mencuri tanpa malu-malu memperluas [b[b==x:]for b in A]seperti yang disarankan oleh jawaban Neil bukannya enumeratependekatan yang lebih lama .

Mengambil daftar daftar Asebagai input. Jika semua elemen Akosong, maka daftar yang dievaluasi ifakan kosong, jadi kami telah mencapai akhir rekursi dan bisa print. Kalau tidak, kami memiliki daftar satu atau lebih None; dan kami berulang.

Jelly , 11 byte

FŒ!fЀ⁼ṛɗÐf

Cobalah online!

Bagaimana itu bekerja

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 byte

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

Jika tidak ada urutan yang tidak kosong, kembalikan urutan yang kosong. Jika tidak, untuk setiap urutan yang tidak kosong, ulangi dengan elemen pertama yang dihapus kemudian tambahkan ke awal setiap hasil. Implementasi menggunakan asumsi bahwa elemen dijamin unik secara global, jika a-[b]tidak berpotensi menghapus lebih dari 1 urutan dari panggilan rekursif. Meskipun dalam refleksi, mungkin itu sebenarnya perilaku yang tepat untuk menghindari duplikat hasil

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

Bahasa Wolfram (Mathematica) , 76 75 71 byte

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

Cobalah online!

Pendekatan naif: temukan semua permutasi yang merupakan selingan input.

Penjelasan

Permutations[Join@@#]

Ratakan <input>dan temukan semua permutasi.

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

Temukan semua elemen xsedemikian rupa sehingga ...

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

Ganti semua item di kedalaman-2 <input>dengan posisi masing-masing di x.

And@@OrderedQ/@ ...

Periksa apakah semua daftar kedalaman-1 dipesan (yaitu dalam urutan meningkat).

Implementasi aktual interleaving, 117 byte

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

Cobalah online!

Python 2 , 87 84 byte

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

Cobalah online! Port jawaban JavaScript saya. Sunting: Disimpan 3 byte berkat @ChasBrown.

Haskell , 45 byte

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

Cobalah online!

Diadaptasi dari jawaban Python Chas Brown .

Ini max[[]]adalah trik untuk memberikan kasus dasar [[]]ketika input hanya berisi []elemen. Dalam hal ini, daftar yang digunakan untuk kosong, berulang adalah kosong, dan max[[]][]memberi [[]].

Saat berulang, alih-alih secara selektif menjatuhkan elemen pertama dari daftar yang dipilih h:t, kami membuat daftar baru dengan tdi bagian depan dan h:tmemfilter.

JavaScript (Firefox 30-57), 92 byte

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 byte

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.

Mengambil input sebagai array array. -Qmembuat output mempertahankan notasi array.

Coba di sini.

Scala: (tidak dimaksudkan untuk menjadi minimal, lebih banyak sumber referensi yang jelas)

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

Cobalah online!