Ostatnio miałem problem do rozwiązania w pracy, gdzie miałem dwie listy: listę główną i mniejszą listę, która zawiera podzbiór elementów na liście głównej potencjalnie w innej kolejności. Musiałem zmienić kolejność listy głównej w taki sposób, aby elementy w podzestawie pojawiały się w tej samej kolejności, bez zmiany kolejności elementów nie znajdujących się na liście i utrzymywania elementów w tej samej lokalizacji, gdy tylko jest to możliwe. Okej, to chyba brzmi myląco, więc podzielę to:

• Lista główna określa domyślną kolejność elementów.
• Lista podzbiorów określa względną kolejność niektórych elementów.
• W przypadku, gdy lista główna zawiera dwa elementy niesprawne zgodnie z listą podzbiorów, element znajdujący się wcześniej na liście głównej powinien zostać przeniesiony do najwcześniejszego indeksu, gdzie znajduje się we właściwej lokalizacji względem innych elementów na liście podzbiorów. (tj. natychmiast po późniejszym elemencie)

Twoim zadaniem jest wdrożenie tego algorytmu zmiany kolejności.

Przykładowe przypadki testowe

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]

Zasady

• Standardowe luki, yadda yadda, wygodne we / wy, bla bla.
• Mimo że w przykładach używane są liczby i ciągi, wystarczy tylko jeden typ elementu, niezależnie od tego, czy są to liczby całkowite, ciągi, czy cokolwiek innego z dobrze zdefiniowaną semantyką równości, w tym listy heterogeniczne, jeśli jest to wygodne w twoim języku.
• Możesz założyć, że zarówno lista główna, jak i lista podzbiorów nie zawierają duplikatów
• Możesz założyć, że wszystkie elementy znajdujące się na liście podzbiorów znajdują się na liście głównej
• Każda lista może być pusta
• Musisz co najmniej obsługiwać tablice o długości do 100 elementów.
• Zmiana kolejności może być realizowana w miejscu lub poprzez utworzenie nowej listy / tablicy.

Wesołego golfa!

Retina 0.8.2 , 51 bajtów

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

Wypróbuj online! Pobiera dane wejściowe jako rozdzieloną przecinkami listę słów podrzędnych w pierwszym wierszu i rozdzieloną przecinkami główną listę słów w drugim wierszu. Wyjaśnienie:

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

Znajdź dwa sąsiednie słowa, w których drugie słowo poprzedza pierwsze na liście głównej.

$1$4,$3

Przenieś drugie słowo, aby pojawiło się po pierwszym słowie na liście głównej.

+`

Powtarzaj, aż żadne słowa nie pojawią się w porządku.

1A`

Usuń słowa podrzędne.

JavaScript (ES6),  96 89 74  71 bajtów

Zaczęło się od nieporęcznego bałaganu i ostatecznie zostało zmniejszone do dość zwięzłej i eleganckiej formy. Chciałbym podziękować metodzie .splice () za owocną współpracę w tej dziedzinie. ;)

Pobiera dane wejściowe jako (master)(subset). Dane wyjściowe poprzez aktualizację listy głównej.

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

Wypróbuj online!

W jaki sposób?

$i$$p$

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

$1$

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

$0$

• wewnętrzna .splice () niczego nie usuwa i zwraca pustą tablicę
• w rezultacie zewnętrzna .splice () otrzymuje niezdefiniowany jako trzeci argument i nic też nie jest wstawiane

Skomentował

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

(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

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

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

Wypróbuj online!

W jaki sposób?

• Przecięcie między ai bzawiera wszystkie elementyb , ale w takiej samej kolejności, w jakiej byśmy je znaleźlia
• Jeśli więc będziemy iterować brównolegle na skrzyżowaniu, gdy tylko znajdziemy różnicę, możemy przenieść pojedynczy element.
• Relokacji dokonuje się poprzez wycięcie apozycji elementu, w którym znaleźliśmyb , a następnie usunięcie elementu, który znaleźliśmy na skrzyżowaniu, a następnie dodanie pozostałej części znaku.
• Powtarzaj od początku, aż wszystkie elementy bbędą w odpowiedniej kolejnościa

Python 2 , 124 109 106 99 96 bajtów

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

Wypróbuj online!

Perl 6 , 40 bajtów

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

Wypróbuj online!

Anonimowy blok kodu, który pobiera dane wejściowe curry (jak f(subList)(masterList)i znajduje pierwszą permutację leksykalną indeksów listy głównej, w której elementy z listy podrzędnej są w odpowiedniej kolejności.

Intuicyjnie pierwsza satysfakcjonująca permutacja pozostawi poprawnie uporządkowane elementy w pierwotnej kolejności, przesuwając niepoprawnie rozmieszczone elementy minimalną potrzebną odległość do przodu, aby uzyskać je we właściwej kolejności, co umieszcza je bezpośrednio za poprzednim elementem w podzbiorze.

Wyjaśnienie:

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

Galaretka , 9 bajtów

Œ!iⱮṢƑ¥ƇḢ

Wypróbuj online! lub pakiet testowy

Nieefektywne, szczególnie w przypadku dużych list głównych. Generuje wszystkie możliwe permutacje, odfiltrowuje te, w których podzbiór ma niewłaściwą kolejność, a następnie zwraca pierwszy.

Wyjaśnienie

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

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

Wypróbuj online!

wyjaśnienie

Przyjmujemy podzbiór jako lewy argument, a pełne dane wejściowe jako prawy.

Przeanalizujemy kod z konkretnym przykładem dla przejrzystości:

5 2 4 f 1 2 3 4 5

Weź pudełkowe przyrostki rozmiaru drugiego podzbioru:

2 <\ [

produkujący:

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

dołącz je do oryginalnych danych wejściowych i odwróć całość:

] |.@;

Otrzymujemy:

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

Rozwiązanie powyższego problemu staje się od prawej do lewej. Musimy tylko znaleźć odpowiedni czasownik do wstawienia/ między elementy.

Każda iteracja redukcji aktualizuje skrajnie prawe pole (pełne wejście, które przekształcamy), aby było zgodne z ograniczeniem porządkowania reprezentowanym przez parę po jego lewej stronie. Po zakończeniu redukcji dane wejściowe będą respektować całą kolejność podzbiorów.

Jeśli kolejność pary jest taka sama jak kolejność na wejściu, następujące wartości zostaną ocenione na 0 i nie zrobimy nic:

^:(>/@i.~)

W przeciwnym razie będzie miało wartość 1 i zastosujemy czasownik po lewej stronie ^:

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

który przesuwa lewy element na prawo od prawego elementu. Ten ruch jest po prostu cykliczną permutacją wszystkich elementów pomiędzy (i włącznie) dwoma przedmiotowymi elementami.

J ma prymitywne zastosowanie takiej cyklicznej permutacji:

<cyclic permutation definition> C. ]

a pozostała część czasownika nie robi nic poza wybraniem indeksów, które musimy cyklicznie zmieniać:

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

co wydaje się dłuższe niż powinno, ale nie mogłem dalej grać w golfa.

Wreszcie ponownie przepakowujemy wynik <@i gotowe.

Galaretka , 24 bajty

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

Wypróbuj online! lub pakiet testowy

Wyjaśnienie

Dyadyczny link, który przyjmuje podzbiór jako lewą, a główną listę jako prawe argumenty. Poniższy przykład wykorzystuje 9001, 42, 69, 1337, 420, 99, 255 jako master i 69, 9001, 1337 jako podzbiór.

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 # (interaktywny kompilator Visual C #) , 118 bajtów

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

Wypróbuj online!

Wykorzystanie niektórych klas w System.Collections.Genericprzestrzeni nazw. Wzorzec to a, List<T>a podzbiór to 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);
    }
}