J'ai récemment eu un problème à résoudre au travail où j'avais deux listes: une liste principale et une liste plus petite qui contient un sous-ensemble des éléments de la liste principale potentiellement dans un ordre différent. Je devais réorganiser la liste principale de manière à ce que les éléments du sous-ensemble apparaissent dans le même ordre sans modifier l'ordre des éléments non trouvés dans la liste et en gardant les éléments au même endroit dans la mesure du possible. D'accord, cela semble probablement déroutant, alors je vais le détailler:

• La liste principale définit l'ordre par défaut des éléments.
• La liste des sous-ensembles définit l'ordre relatif de certains éléments.
• Lorsque la liste principale contient deux éléments en désordre selon la liste de sous-ensembles, l'élément qui se trouve plus tôt dans la liste principale doit être déplacé vers le premier index où il se trouve au bon emplacement par rapport aux autres éléments de la liste de sous-ensembles. (c'est-à-dire immédiatement après le dernier élément)

Votre tâche consiste à implémenter cet algorithme de réorganisation.

Exemples de cas de test

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]

Règles

• Failles standard, yadda yadda, E / S pratiques, bla bla.
• Même si les exemples utilisent des nombres et des chaînes, vous ne devez prendre en charge qu'un seul type d'élément, qu'il s'agisse d'entiers, de chaînes ou de tout autre élément avec une sémantique d'égalité bien définie, y compris des listes hétérogènes si cela vous convient dans votre langue.
• Vous pouvez supposer que la liste principale et la liste de sous-ensembles ne contiennent aucun doublon
• Vous pouvez supposer que tous les éléments trouvés dans la liste des sous-ensembles se trouvent dans la liste principale
• L'une ou l'autre liste peut être vide
• Vous devez, au minimum, prendre en charge des tableaux jusqu'à 100 éléments.
• La réorganisation peut être implémentée sur place ou par la création d'une nouvelle liste / tableau.

Bon golf!

Retina 0.8.2 , 51 octets

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

Essayez-le en ligne! Prend l'entrée comme une liste de sous-mots séparés par des virgules sur la première ligne et une liste principale de mots séparés par des virgules sur la deuxième ligne. Explication:

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

Trouvez deux sous-mots adjacents où le deuxième mot précède le premier de la liste principale.

$1$4,$3

Déplacez le deuxième mot pour qu'il apparaisse après le premier mot de la liste principale.

+`

Répétez jusqu'à ce qu'aucun mot n'apparaisse en désordre.

1A`

Supprimez les sous-mots.

JavaScript (ES6),  96 89 74  71 octets

Cela a commencé comme un désordre encombrant et a finalement été réduit à une forme plutôt concise et élégante. Je remercie la méthode .splice () pour sa collaboration fructueuse sur celle-ci. ;)

Prend l'entrée comme (master)(subset). Sorties en mettant à jour la liste principale.

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

Essayez-le en ligne!

Comment?

Nous utilisons deux imbriqués $i$$p$

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

$1$

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

$0$

• le .splice () intérieur ne supprime rien et renvoie un tableau vide
• en conséquence, le .splice () externe reçoit undefined comme son troisième argument et rien n'est inséré non plus

Commenté

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 octets

(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

Essayez-le en ligne!

(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

Rubis , 73 68 octets

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

Essayez-le en ligne!

Comment?

• L'intersection entre aet bcontient tous les éléments de b, mais dans le même ordre que nous les trouverions dansa
• Donc, si nous itérons sur bet sur l'intersection en parallèle, dès que nous trouvons une différence, nous pouvons déplacer un seul élément.
• La réinstallation se fait en coupant ala position de l'élément dans lequel nous avons trouvé b, puis en supprimant l'élément que nous avons trouvé dans l'intersection, puis en ajoutant le reste de a.
• Répétez depuis le début, jusqu'à ce que tous les éléments de bsoient dans le bon ordrea

Python 2 , 124 109 106 106 99 96 octets

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

Essayez-le en ligne!

Perl 6 , 40 octets

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

Essayez-le en ligne!

Bloc de code anonyme qui prend le curry d'entrée (comme f(subList)(masterList), et trouve la première permutation lexographique des index de la liste principale où les éléments de la sous-liste sont dans le bon ordre.

Intuitivement, la première permutation satisfaisante laissera les éléments correctement ordonnés dans l'ordre d'origine, tout en déplaçant ceux mal placés la distance minimale nécessaire vers l'avant afin de les avoir dans l'ordre correct, ce qui les place directement après l'élément précédent dans le sous-ensemble.

Explication:

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

Gelée , 9 octets

Œ!iⱮṢƑ¥ƇḢ

Essayez-le en ligne! ou Suite de tests

Inefficace, en particulier avec de grandes listes principales. Génère toutes les permutations possibles, filtre celles dont le sous-ensemble est dans le mauvais ordre, puis renvoie la première.

Explication

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

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

Essayez-le en ligne!

explication

Nous prenons le sous-ensemble comme argument gauche et l'entrée complète comme droite.

Nous allons travailler sur le code avec un exemple spécifique pour plus de clarté:

5 2 4 f 1 2 3 4 5

Prenez les infixes encadrés de taille deux du sous-ensemble:

2 <\ [

produisant:

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

ajoutez-les à l'entrée d'origine et inversez le tout:

] |.@;

On a:

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

La résolution du problème devient une réduction de droite à gauche sur ce qui précède. Il suffit de trouver le bon verbe à insérer/ entre les éléments.

Chaque itération de la réduction mettra à jour la case la plus à droite (l'entrée complète, que nous transformons) afin qu'elle soit conforme à la contrainte de commande représentée par la paire à sa gauche. Une fois la réduction terminée, l'entrée respectera l'ordre de sous-ensemble complet.

Si l'ordre de la paire est le même que l'ordre dans l'entrée, ce qui suit sera évalué à 0 et nous ne ferons rien:

^:(>/@i.~)

Sinon, il sera évalué à 1 et nous appliquerons le verbe à gauche de ^:

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

qui déplace l'élément gauche vers la droite de l'élément droit. Ce mouvement est simplement une permutation cyclique de tous les éléments entre (et y compris) les deux éléments en question.

J a primitif pour appliquer une telle permutation cyclique:

<cyclic permutation definition> C. ]

et le reste du verbe ne fait que sélectionner les index dont nous avons besoin pour faire un cycle:

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

ce qui semble plus long qu'il ne devrait l'être, mais je n'ai pas pu jouer plus loin cette phrase.

Enfin, nous rebox le résultat <@et nous avons terminé.

Gelée , 24 octets

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

Essayez-le en ligne! ou Suite de tests

Explication

Un lien dyadique qui prend le sous-ensemble comme gauche et la liste principale comme arguments de droite. L'exemple ci-dessous utilise 9001, 42, 69, 1337, 420, 99, 255 comme maître et 69, 9001, 1337 comme sous-ensemble.

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 octets

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

Essayez-le en ligne!

Tirer parti de certaines classes de l' System.Collections.Genericespace de noms. Le maître est un List<T>et le sous-ensemble est un 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);
    }
}