Recientemente tuve un problema que resolver en el trabajo donde tenía dos listas: una lista maestra y una lista más pequeña que contiene un subconjunto de los elementos de la lista maestra potencialmente en un orden diferente. Necesitaba reordenar la lista maestra de tal manera que los elementos del subconjunto aparecieran en el mismo orden sin cambiar el orden de los elementos que no se encuentran en la lista y mantener los elementos en la misma ubicación siempre que sea posible. De acuerdo, eso probablemente suene confuso, así que lo desglosaré:

• La lista maestra define el orden predeterminado de los elementos.
• La lista de subconjuntos define el orden relativo de ciertos elementos.
• Cuando la lista maestra tiene dos elementos desordenados de acuerdo con la lista de subconjuntos, el elemento que está más temprano en la lista maestra debe moverse al índice más temprano donde se encuentra en la ubicación correcta en relación con otros elementos dentro de la lista de subconjuntos. (es decir, inmediatamente después del artículo posterior)

Su tarea es implementar este algoritmo de reordenamiento.

Ejemplos de casos de prueba

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]

Reglas

• Lagunas estándar, yadda yadda, E / S conveniente, bla, bla.
• Aunque los ejemplos usan números y cadenas, solo necesita admitir un tipo de elemento, ya sean enteros, cadenas o cualquier otra cosa con una semántica de igualdad bien definida, incluidas listas heterogéneas si es conveniente en su idioma.
• Puede suponer que tanto la lista maestra como la lista de subconjuntos no contienen duplicados
• Puede suponer que todos los elementos encontrados en la lista de subconjuntos se encuentran en la lista maestra
• Cualquiera de las listas puede estar vacía
• Debe, como mínimo, admitir matrices de hasta 100 elementos de largo.
• El reordenamiento puede implementarse en el lugar o mediante la creación de una nueva lista / matriz.

¡Feliz golf!

Retina 0.8.2 , 51 bytes

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

Pruébalo en línea! Toma datos como una lista de subpalabras separadas por comas en la primera línea y una lista maestra de palabras separadas por comas en la segunda línea. Explicación:

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

Encuentre dos subpalabras adyacentes donde la segunda palabra precede a la primera en la lista maestra.

$1$4,$3

Mueva la segunda palabra para que aparezca después de la primera palabra en la lista maestra.

+`

Repita hasta que no aparezcan palabras fuera de orden.

1A`

Eliminar las subpalabras.

JavaScript (ES6),  96 89 74  71 bytes

Esto comenzó como un desastre voluminoso y finalmente se redujo a una forma bastante concisa y elegante. Me gustaría agradecer a los método .splice () por su fructífera colaboración en ese sentido. ;)

Toma entrada como (master)(subset). Salidas actualizando la lista maestra.

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

Pruébalo en línea!

¿Cómo?

$i$$p$

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

$1$

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

$0$ ):

• el interior .splice () no elimina nada y devuelve una matriz vacía
• como resultado, el .splice externo () recibe indefinido como su tercer argumento y tampoco se inserta nada

Comentado

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

Pruébalo en línea!

(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

rubí , 73 68 bytes

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

Pruébalo en línea!

¿Cómo?

• La intersección entre ayb contiene todos los elementos deb , pero en el mismo orden en que los encontraríamos ena
• Entonces, si iteramos en b y en la intersección en paralelo, tan pronto como encontremos una diferencia, podemos reubicar un solo elemento.
• La reubicación se realiza cortando ala posición del elemento que encontramos enb , luego eliminando el elemento que encontramos en la intersección y luego agregando el resto de a.
• Repita desde el principio, hasta que todos los elementos bestén en el orden correcto ena

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

Pruébalo en línea!

Perl 6 , 40 bytes

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

Pruébalo en línea!

Bloque de código anónimo que toma la entrada al curry (como f(subList)(masterList), y encuentra la primera permutación lexográfica de los índices de la lista maestra donde los elementos de la sublista están en el orden correcto.

Intuitivamente, la primera permutación satisfactoria dejará los elementos correctamente ordenados en el orden original, mientras mueve a los incorrectamente colocados la distancia mínima necesaria hacia adelante para tenerlos en el orden correcto, que los coloca directamente después del elemento anterior en el subconjunto.

Explicación:

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

Jalea , 9 bytes

Œ!iⱮṢƑ¥ƇḢ

Pruébalo en línea! o conjunto de pruebas

Ineficiente, particularmente con grandes listas maestras. Genera todas las permutaciones posibles, filtra aquellas en las que el subconjunto está en el orden incorrecto y luego devuelve el primero.

Explicación

Œ!        | 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<\[

Pruébalo en línea!

explicación

Tomamos el subconjunto como el argumento izquierdo y la entrada completa como el derecho.

Trabajaremos a través del código con un ejemplo específico para mayor claridad:

5 2 4 f 1 2 3 4 5

Tome los infijos en caja de tamaño dos del subconjunto:

2 <\ [

productor:

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

agréguelos a la entrada original e invierta todo:

] |.@;

Obtenemos:

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

Resolver el problema se convierte en una reducción de derecha a izquierda en lo anterior. Solo necesitamos encontrar el verbo correcto para insertar/ entre los elementos.

Cada iteración de la reducción actualizará el cuadro de la derecha (la entrada completa, que estamos transformando) para que se ajuste a la restricción de ordenamiento representada por el par a su izquierda. Cuando finaliza la reducción, la entrada respetará el orden completo del subconjunto.

Si el orden del par es el mismo que el pedido en la entrada, lo siguiente se evaluará a 0 y no haremos nada:

^:(>/@i.~)

De lo contrario, se evaluará a 1 y aplicaremos el verbo a la izquierda de ^:

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

que mueve el elemento izquierdo a la derecha del elemento derecho. Este movimiento es simplemente una permutación cíclica. de todos los elementos entre (e incluyendo) los dos elementos en cuestión.

J tiene primitivo para aplicar una permutación cíclica de este tipo:

<cyclic permutation definition> C. ]

y el resto del verbo no hace más que seleccionar los índices que necesitamos para completar el ciclo:

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

que parece más largo de lo que debería ser, pero no pude seguir esa frase.

Finalmente volvemos a encajonar el resultado <@y terminamos.

Jalea , 24 bytes

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

Pruébalo en línea! oconjunto de pruebas

Explicación

Un enlace diádico que toma el subconjunto como la izquierda y la lista maestra como argumentos correctos. El siguiente ejemplo utiliza 9001, 42, 69, 1337, 420, 99, 255 como maestro y 69, 9001, 1337 como subconjunto.

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 # (compilador interactivo de Visual C #) , 118 bytes

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

Pruébalo en línea!

Aprovechando algunas clases en el System.Collections.Genericespacio de nombres. El maestro es a List<T>y el subconjunto es 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);
    }
}