Ich hatte kürzlich ein Problem bei der Arbeit zu lösen, bei dem ich zwei Listen hatte: eine Hauptliste und eine kleinere Liste, die eine Teilmenge der Elemente in der Hauptliste möglicherweise in einer anderen Reihenfolge enthält. Ich musste die Hauptliste so neu anordnen, dass die Elemente in der Teilmenge in derselben Reihenfolge angezeigt wurden, ohne die Reihenfolge der nicht in der Liste gefundenen Elemente zu ändern, und die Elemente nach Möglichkeit an derselben Stelle aufbewahren. Okay, das klingt wahrscheinlich verwirrend, also werde ich es aufschlüsseln:

• Die Hauptliste definiert die Standardreihenfolge der Elemente.
• Die Teilmengenliste definiert die relative Reihenfolge bestimmter Elemente.
• Wenn die Hauptliste zwei Elemente enthält, die gemäß der Teilmengenliste nicht in der richtigen Reihenfolge sind, sollte das Element, das sich früher in der Hauptliste befindet, in den frühesten Index verschoben werden, in dem es sich relativ zu anderen Elementen in der Teilmengenliste an der richtigen Stelle befindet. (dh unmittelbar nach dem späteren Punkt)

Ihre Aufgabe ist es, diesen Neuordnungsalgorithmus zu implementieren.

Beispiel Testfälle

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]

Regeln

• Standard Schlupflöcher, Yadda Yadda, bequeme I / O, bla bla.
• Obwohl in den Beispielen Zahlen und Zeichenfolgen verwendet werden, müssen Sie nur einen Elementtyp unterstützen, unabhängig davon, ob es sich um Ganzzahlen, Zeichenfolgen oder andere Elemente mit genau definierter Gleichheitssemantik handelt, einschließlich heterogener Listen, sofern dies in Ihrer Sprache sinnvoll ist.
• Sie können davon ausgehen, dass sowohl die Master-Liste als auch die Subset-Liste keine Duplikate enthalten
• Sie können davon ausgehen, dass sich alle in der Teilmengenliste gefundenen Elemente in der Masterliste befinden
• Jede Liste kann leer sein
• Sie müssen mindestens Arrays mit einer Länge von bis zu 100 Elementen unterstützen.
• Die Neuordnung kann vor Ort oder durch die Erstellung einer neuen Liste / eines neuen Arrays implementiert werden.

Viel Spaß beim Golfen!

Retina 0,8,2 , 51 Bytes

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

Probieren Sie es online! Übernimmt die Eingabe als durch Kommas getrennte Liste von Unterwörtern in der ersten Zeile und als durch Kommas getrennte Hauptliste von Wörtern in der zweiten Zeile. Erläuterung:

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

Finden Sie zwei benachbarte Unterwörter, wobei das zweite Wort dem ersten in der Hauptliste vorausgeht.

$1$4,$3

Bewegen Sie das zweite Wort nach dem ersten Wort in der Hauptliste.

+`

Wiederholen, bis keine Wörter mehr in der falschen Reihenfolge angezeigt werden.

1A`

Löschen Sie die Unterwörter.

JavaScript (ES6),  96 89 74  71 Byte

Dies begann als sperriges Durcheinander und wurde schließlich zu einer ziemlich prägnanten und eleganten Form geschrumpft. Ich möchte mich bei der .splice () -Methode für die fruchtbare Zusammenarbeit bedanken . ;)

Übernimmt die Eingabe als (master)(subset). Ausgaben durch Aktualisierung der Masterliste.

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

Probieren Sie es online!

Wie?

$i$$p$

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

$1$

• $i$$[element]$
• Dank der Spread-Syntax wird dieses Element als drittes Argument für das äußere .splice () erweitert , wodurch es wieder an der Position eingefügt wird$p$

$0$

• Das innere .splice () entfernt nichts und gibt ein leeres Array zurück
• Infolgedessen erhält das äußere .splice () als drittes Argument ein undefiniertes Argument, und es wird auch nichts eingefügt

Kommentiert

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 Bytes

(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

Probieren Sie es 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

Ruby , 73 68 Bytes

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

Probieren Sie es online!

Wie?

• Der Schnittpunkt zwischen aund benthält alle Elemente von b, jedoch in derselben Reihenfolge, in der wir sie finden würdena
• Wenn wir also bparallel auf und an der Kreuzung iterieren , können wir ein einzelnes Element verschieben, sobald wir einen Unterschied feststellen.
• Die Verschiebung erfolgt durch Ausschneiden ader Position des Elements, in dem wir gefunden haben b, Entfernen des Elements, das wir in der Schnittmenge gefunden haben, und Hinzufügen des Restes von a.
• Wiederholen Sie dies von Anfang an, bis alle Elemente von bin der richtigen Reihenfolge sinda

Python 2 , 124 109 106 99 96 Bytes

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

Probieren Sie es online!

Perl 6 , 40 Bytes

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

Probieren Sie es online!

Anonymer Codeblock, der die Eingabe als Curry f(subList)(masterList)akzeptiert ( und die erste lexografische Permutation der Indizes der Master-Liste findet, in der sich die Elemente aus der Unterliste in der richtigen Reihenfolge befinden).

Intuitiv belässt die erste zufriedenstellende Permutation die richtig angeordneten Elemente in der ursprünglichen Reihenfolge, während die falsch angeordneten Elemente um den minimal erforderlichen Abstand nach vorne verschoben werden, um sie in der richtigen Reihenfolge zu haben, wodurch sie direkt nach dem vorherigen Element in der Teilmenge platziert werden.

Erläuterung:

{*                                     } # 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

Gelee , 9 Bytes

Œ!iⱮṢƑ¥ƇḢ

Probieren Sie es online! oder Testsuite

Ineffizient, insbesondere bei großen Masterlisten. Generiert alle möglichen Permutationen, filtert diejenigen heraus, bei denen sich die Teilmenge in der falschen Reihenfolge befindet, und gibt dann die erste zurück.

Erläuterung

Œ!        | 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 Bytes

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

Probieren Sie es online!

Erläuterung

Wir nehmen die Teilmenge als linkes Argument und die volle Eingabe als rechtes.

Der Übersichtlichkeit halber werden wir den Code anhand eines speziellen Beispiels durcharbeiten:

5 2 4 f 1 2 3 4 5

Nehmen Sie die boxed Infixes der Größe zwei der Teilmenge:

2 <\ [

produzieren:

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

Hänge sie an die ursprüngliche Eingabe an und kehre das Ganze um:

] |.@;

Wir bekommen:

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

Die Lösung des Problems führt zu einer Reduzierung von rechts nach links. Wir müssen nur das richtige Verb finden, um es /zwischen die Elemente einzufügen .

Bei jeder Iteration der Verkleinerung wird das Feld ganz rechts (die vollständige Eingabe, die wir transformieren) aktualisiert, sodass es der durch das Paar auf der linken Seite dargestellten Ordnungsbeschränkung entspricht. Wenn die Reduzierung abgeschlossen ist, berücksichtigt die Eingabe die vollständige Teilmengenreihenfolge.

Wenn die Reihenfolge des Paares mit der Reihenfolge in der Eingabe übereinstimmt, wird Folgendes mit 0 ausgewertet, und es wird nichts unternommen:

^:(>/@i.~)

Andernfalls wird 1 ausgewertet und das Verb links von angewendet ^:

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

Das verschiebt das linke Element nach rechts vom rechten Element. Diese Bewegung ist einfach eine zyklische Permutation aller Elemente zwischen (und einschließlich) den zwei fraglichen Elementen.

J hat eine Grundform, um eine solche zyklische Permutation anzuwenden:

<cyclic permutation definition> C. ]

und der Rest des Verbs tut nichts anderes, als die Indizes auszuwählen, die wir zum Durchlaufen benötigen:

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

Das scheint länger zu sein, als es sein sollte, aber ich war nicht in der Lage, diesen Satz weiter zu spielen.

Schließlich packen wir das Ergebnis neu <@und wir sind fertig.

Gelee , 24 Bytes

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

Probieren Sie es online! oder Testsuite

Erläuterung

Eine dyadische Verknüpfung, die die Teilmenge als linkes und die Hauptliste als rechtes Argument verwendet. Im folgenden Beispiel werden 9001, 42, 69, 1337, 420, 99, 255 als Master und 69, 9001, 1337 als Teilmenge verwendet.

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

Probieren Sie es online!

Nutzung einiger Klassen im System.Collections.GenericNamespace. Der Master ist a List<T>und die Teilmenge ist 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);
    }
}