Saya baru-baru ini memiliki masalah untuk dipecahkan di tempat kerja di mana saya memiliki dua daftar: daftar master, dan daftar yang lebih kecil yang berisi subset item dalam daftar master yang berpotensi dalam urutan yang berbeda. Saya perlu menyusun ulang daftar master sedemikian rupa sehingga item dalam subset akan muncul dalam urutan yang sama tanpa mengubah urutan item yang tidak ditemukan dalam daftar dan menyimpan item di lokasi yang sama jika memungkinkan. Oke, itu mungkin terdengar membingungkan, jadi saya akan memecahnya:

• Daftar master mendefinisikan urutan item default.
• Daftar subset mendefinisikan urutan relatif dari item tertentu.
• Jika daftar master memiliki dua elemen yang tidak sesuai dengan daftar subset, item yang sebelumnya dalam daftar master harus dipindahkan ke indeks paling awal di mana ia berada di lokasi yang benar relatif terhadap item lain dalam daftar subset. (Yaitu segera setelah item kemudian)

Tugas Anda adalah mengimplementasikan algoritma pemesanan ulang ini.

Contoh Kasus Uji

Master: [1, 2, 3]
Subset: []
Result: [1, 2, 3]

Master: [9001, 42, 69, 1337, 420]
Subset: [69]
Result: [9001, 42, 69, 1337, 420]

Master: [9001, 42, 69, 1337, 420, 99, 255]
Subset: [69, 9001, 1337]
Result: [42, 69, 9001, 1337, 420, 99, 255]

Master: [1, 2, 3, 4, 5]
Subset: [2, 5]
Result: [1, 2, 3, 4, 5]

Master: [apple, banana, carrot, duck, elephant]
Subset: [duck, apple]
Result: [banana, carrot, duck, apple, elephant]

Master: [Alice, Betty, Carol, Debbie, Elaine, Felicia, Georgia, Helen, Ilene, Julia]
Subset: [Betty, Felicia, Carol, Julia]
Result: [Alice, Betty, Debbie, Elaine, Felicia, Carol, Georgia, Helen, Ilene, Julia]

Master: [snake, lizard, frog, werewolf, vulture, dog, human]
Subset: [snake, werewolf, lizard, human, dog]
Result: [snake, frog, werewolf, lizard, vulture, human, dog]

Master: [Pete, Rob, Jeff, Stan, Chris, Doug, Reggie, Paul, Alex]
Subset: [Jeff, Stan, Pete, Paul]
Result: [Rob, Jeff, Stan, Pete, Chris, Doug, Reggie, Paul, Alex]

Master: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
Subset: [8, 1, 2, 12, 11, 10]
Result: [3, 4, 5, 6, 7, 8, 1, 2, 9, 12, 11, 10]

Master: [lol, rofl, lmao, roflmao, lqtm, smh, jk, wat]
Subset: [wat, lmao, rofl]
Result: [lol, roflmao, lqtm, smh, jk, wat, lmao, rofl]

Aturan

• Celah standar, yadda yadda, I / O yang nyaman, bla bla.
• Meskipun contoh menggunakan angka dan string, Anda hanya perlu mendukung satu jenis elemen, apakah itu bilangan bulat, string, atau apa pun dengan semantik kesetaraan yang terdefinisi dengan baik, termasuk daftar heterogen jika sesuai dengan bahasa Anda.
• Anda dapat mengasumsikan daftar master dan daftar subset tidak mengandung duplikat
• Anda dapat mengasumsikan bahwa semua item yang ditemukan dalam daftar subset ditemukan dalam daftar master
• Daftar mana pun mungkin kosong
• Anda harus, minimal, mendukung array hingga 100 elemen.
• Penataan ulang dapat diimplementasikan di tempat atau melalui pembuatan daftar / larik baru.

Selamat Golf!

Retina 0.8.2 , 51 byte

+`(\b(\w+),(\w+)\b.*¶.*\b)\3,(.*\b\2\b)
$1$4,$3
1A`

Cobalah online! Mengambil input sebagai daftar subword yang dipisahkan koma pada baris pertama dan daftar kata utama yang dipisahkan koma pada baris kedua. Penjelasan:

(\b(\w+),(\w+)\b.*¶.*\b)\3,(.*\b\2\b)

Temukan dua subword yang berdekatan di mana kata kedua mendahului yang pertama pada daftar master.

$1$4,$3

Pindahkan kata kedua yang muncul setelah kata pertama dalam daftar master.

+`

Ulangi sampai tidak ada kata yang keluar dari urutan.

1A`

Hapus subtitle.

JavaScript (ES6),  96 89 74  71 byte

Ini dimulai sebagai kekacauan besar dan akhirnya menyusut ke bentuk yang agak ringkas dan elegan. Saya ingin mengucapkan terima kasih .splice () atas kolaborasi yang bermanfaat untuk yang satu itu. ;)

Mengambil input sebagai (master)(subset). Keluaran dengan memperbarui daftar master.

m=>s=>s.map(p=x=>m.splice(p,0,...m.splice(i=m.indexOf(x),p>i||!(p=i))))

Cobalah online!

Bagaimana?

$i$$p$

m.splice(p, 0, ...m.splice(i, condition))

$1$

• $i$$[element]$
• $p$

$0$

• bagian dalam .plice () menghapus apa-apa dan mengembalikan array kosong
• sebagai hasilnya, outer .splice () menerima undefined sebagai argumen ke-3 dan tidak ada yang dimasukkan

Berkomentar

m => s =>                 // m[] = master list, s[] = subset list
  s.map(                  //
    p =                   // p = position in the master list of the last element from
                          //     the subset list (initialized to a non-numeric value)
    x =>                  // for each element x in the subset list:
    m.splice(             //   insert in the master list:
      p,                  //     at position p
      0,                  //     without removing any element
      ...m.splice(        //     remove from the master list and flatten:
        i = m.indexOf(x), //       i = position of x in the master list
        p > i             //       if p is greater than i, remove x from its current
                          //       position and insert it at position p
        || !(p = i)       //       otherwise, set p to i and don't remove/insert anything
      )                   //     end of inner splice()
    )                     //   end of outer splice()
  )                       // end of map()

Haskell, 79 byte

(m:n)#u@(s:t)|m==s=m:n#t|all(/=m)u=m:n#u|(x,_:z)<-span(/=s)n=(x++s:m:z)#u
m#_=m

Cobalah online!

(m:n)#u@(s:t)                 -- m: head of master list
                              -- n: tail of master list
                              -- s: head of subset
                              -- t: tail of subset
                              -- u: whole subset
   |m==s                      -- if m==s
        =m:n#t                -- return 'm' and append a recursive call with 'n' and 't'
   |all(/=m)u                 -- if 'm' is not in 'u'
             =m:n#u           -- return 'm' and append a recursive call with 'n' and 'u'
   |                          -- else (note: 's' is element of 'n')
    (x,_:z)<-span(/=s)n       -- split 'n' into a list 'x' before element 's' and
                              -- a list 'z' after element 's' and
       = (x++s:m:z)#u         -- make a recursive call with
                              -- x++s:m:z as the new master list (i.e. 'm' inserted into 'n' after 's') 
                              -- and 'u'
m # _ = m                     -- if either list is emtpy, return the master list

Rubi , 73 68 byte

->a,b{0while b.zip(a&b).find{|m,n|m!=n&&a=a[0..a.index(m)]-[n]|a};a}

Cobalah online!

Bagaimana?

• Persimpangan antara a dan bberisi semua elemen b, tetapi dalam urutan yang sama seperti yang kita temukana
• Jadi, jika kita beralih di bdan di persimpangan secara paralel, segera setelah kita menemukan perbedaan, kita dapat memindahkan satu elemen.
• Relokasi dilakukan dengan memotong a posisi elemen yang kami temukan b, kemudian menghapus elemen yang kami temukan di persimpangan, dan kemudian menambahkan sisa a.
• Ulangi dari awal, sampai semua elemen bberada di urutan yang benara

Python 2 , 124 109 106 99 96 byte

def f(a,b,i=0):
 while b[i+1:]:x,y=map(a.index,b)[i:i+2];i+=1;x>y>a.insert(x,a.pop(y))
 return a

Cobalah online!

Perl 6 , 40 byte

{*.permutations.first(*.grep(.any)eq$_)}

Cobalah online!

Blok kode anonim yang mengambil input kari (seperti f(subList)(masterList) , dan menemukan permutasi leksografis pertama dari indeks daftar master di mana elemen-elemen dari sub daftar berada dalam urutan yang benar.

Secara intuitif, permutasi memuaskan pertama akan meninggalkan elemen yang diurutkan dengan benar dalam urutan asli, sementara memindahkan yang salah menempatkan jarak minimum yang dibutuhkan ke depan untuk memilikinya dalam urutan yang benar, yang menempatkan mereka langsung setelah elemen sebelumnya di subset.

Penjelasan:

{*                                     } # Anonymous code block that returns a lambda
  .permutations                          # In all permutations of the master list
               .first(                )  # Find the first permutation
                     (*.grep(.any)       # Where the order of the subset
                                  eq$_   # Is the same as the given order

Jelly , 9 byte

Œ!iⱮṢƑ¥ƇḢ

Cobalah online! atau Test suite

Tidak efisien, terutama dengan daftar induk yang besar. Menghasilkan semua permutasi yang mungkin, memfilter orang-orang di mana subset berada dalam urutan yang salah, dan kemudian mengembalikan yang pertama.

Penjelasan

Œ!        | Generate all permutations of the master list
      ¥Ƈ  | Filter including only those where...
  iⱮ      |   the index of each sublist item in this permutation...
     Ƒ    |   is...
    Ṣ     |   in order. 
        Ḣ | Finally take the first item

J , 49 byte

[:(<@({:+i.@>:@-/)@i.~C.])^:(>/@i.~)&.>/]|.@;2<\[

Cobalah online!

penjelasan

Kami mengambil subset sebagai arg kiri dan input penuh sebagai kanan.

Kami akan bekerja melalui kode dengan contoh khusus untuk kejelasan:

5 2 4 f 1 2 3 4 5

Ambil infiks kotak ukuran dua dari subset:

2 <\ [

memproduksi:

┌───┬───┐
│5 2│2 4│
└───┴───┘

menambahkannya ke input asli, dan membalikkan semuanya:

] |.@;

Kita mendapatkan:

┌───┬───┬─────────┐
│2 4│5 2│1 2 3 4 5│
└───┴───┴─────────┘

Memecahkan masalah menjadi pengurangan kanan ke kiri di atas. Kita hanya perlu menemukan kata kerja yang tepat untuk dimasukkan/ antara item.

Setiap iterasi pengurangan akan memperbarui kotak paling kanan (input penuh, yang kami transformasikan) sehingga sesuai dengan batasan pemesanan yang diwakili oleh pasangan di sebelah kiri. Ketika pengurangan selesai, input akan menghormati pemesanan subset lengkap.

Jika pemesanan pasangan sama dengan memesan pada input, yang berikut ini akan dievaluasi menjadi 0 dan kami tidak akan melakukan apa pun:

^:(>/@i.~)

Kalau tidak, akan mengevaluasi ke 1 dan kami akan menerapkan kata kerja di sebelah kiri ^:

   {: + i.@>:@-/)@i.~ C. ]

yang memindahkan item kiri ke kanan item kanan. Gerakan ini hanyalah permutasi siklik dari semua item antara (dan termasuk) dua elemen yang dimaksud.

J memiliki primitif untuk menerapkan permutasi siklik seperti itu:

<cyclic permutation definition> C. ]

dan sisa kata kerja tidak melakukan apa-apa selain memilih indeks yang perlu kita daur:

{: + i.@>:@-/)@i.~

yang tampaknya lebih lama dari yang seharusnya, tetapi saya tidak dapat golf frase itu lebih jauh.

Akhirnya kami melakukan rebox hasilnya <@dan selesai.

Jelly , 24 byte

i@€MƤFṬœṗƲḊ;JḟF}W€ʋ@¥ṢFị

Cobalah online! atau Test suite

Penjelasan

Tautan diad yang menggunakan subset sebagai kiri dan daftar utama sebagai argumen yang benar. Contoh di bawah menggunakan 9001, 42, 69, 1337, 420, 99, 255 sebagai master dan 69, 9001, 1337 sebagai himpunan bagian.

i@€                      | Find the index of each subset item in the master list [3, 1, 4]
         Ʋ               | Previous 4 links as a monad
   MƤ                    | Find the index of the maximum for each prefix of this list [1, 1, 3]
     F                   | Flatten (because the previous result are actually each length one lists)
      Ṭ                  | Convert to a boolean list [1,0,1]
       œṗ                | Partition the [3, 1, 4] list before each 1 [[], [3, 1], [4]]
          Ḋ              | Remove the empty first list [[3, 1], [4]]
                    ¥    | Previous two links as a dyad
                  ʋ@     | Previous 4 links as a dyad with reversed arguments
            J            | Sequence along the master list [1, 2, 3, 4, 5, 6, 7]
             ḟF}         | Filter out items in the flattened [3, 1, 4] list
                W€       | Wrap each item as a list [[2], [5], [6], [7]]
           ;             | Concatenate rhis to the [[3, 1], [4]] list
                     Ṣ   | Sort (effectively by first item in each list) [[2], [3, 1], [4], [5], [6], [7]]
                      F  | Flatten
                       ị | Look up in original master list (and implicitly output)

C # (Visual C # Interactive Compiler) , 118 byte

a=>b=>{for(int j;b.Any();)foreach(var e in b.Intersect(a.Take(j=a.IndexOf(b.Dequeue())))){a.Remove(e);a.Insert(j,e);}}

Cobalah online!

Memanfaatkan beberapa kelas di System.Collections.Genericnamespace. Master adalah a List<T>dan subset adalah a Queue<T>.

// a: master
// b: subset
a=>b=>{
  // continue until b is empty
  for(int j;b.Any();)
    // iterate over values that are out of order in a
    // per the head of b using loop variable e
    foreach(var e in
      // the out of order values are determined by
      // intersecting remaining values in b with
      b.Intersect(
        // values in a occurring before the current head of b
        // save the position in a to variable j and remove the head of b
        a.Take(j=a.IndexOf(b.Dequeue()))
      )
    ){
      // push back the out of order element in a
      a.Remove(e);
      a.Insert(j,e);
    }
}