I recently had a problem to solve at work where I had two lists: a master list, and a smaller list that contains a subset of the items in the master list potentially in a different order. I needed to reorder the master list in such a way that the items in the subset would appear in the same order without changing the order of the items not found in the list and keeping items in the same location whenever possible. Okay, that probably sounds confusing, so I'll break it down:

• The master list defines the default order of items.


• The subset list defines relative order of certain items.


• Where the master list has two elements out of order according to the subset list, the item that is earlier in the master list should be moved to the earliest index where it is in the correct location relative to other items within the subset list. (i.e. immediately after the later item)

Your task is to implement this reordering algorithm.

Example Test Cases

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]

Rules

• Standard loopholes, yadda yadda, convenient I/O, blah blah.


• Even though the examples use numbers and strings, you only need to support one element type, whether that's integers, strings, or anything else with well-defined equality semantics, including heterogeneous lists if that's convenient in your language.


• You may assume both the master list and the subset list contain no duplicates


• You may assume that all items found in the subset list are found in the master list


• Either list may be empty


• You must, at minimum, support arrays up to 100 elements long.


• Reordering may be implemented in-place or through the creation of a new list/array.

Happy Golfing!

Retina 0.8.2, 51 bytes

+`(b(w+),(w+)b.*¶.*b)3,(.*b2b)

$1$4,$3

1A`

Try it online! Takes input as a comma-separated list of subwords on the first line and a comma-separated master list of words on the second line. Explanation:

(b(w+),(w+)b.*¶.*b)3,(.*b2b)

Find two adjacent subwords where the second word precedes the first on the master list.

$1$4,$3

Move the second word to appear after the first word in the master list.

+`

Repeat until no words appear out of order.

1A`

Delete the subwords.

JavaScript (ES6),  96 89 74  71 bytes

This started as a bulky mess and was eventually shrunk to a rather concise and elegant form. I'd like to thank the .splice() method for its fruitful collaboration on that one. ;)

Takes input as (master)(subset). Outputs by updating the master list.

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

Try it online!

How?

We are using two nested .splice() methods on the same array to conditionally move an element from position $i$ to position $p$:

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

If the condition is truthy (coerced to $1$):

• the inner .splice() removes and returns the element at position $i$ as a singleton array $[element]$
  


• thanks to the spread syntax, this element is expanded as a 3rd argument for the outer .splice(), which causes it to be inserted back at position $p$
  

If the condition is falsy (coerced to $0$):

• the inner .splice() removes nothing and returns an empty array


• as a result, the outer .splice() receives undefined as its 3rd argument and nothing is inserted either

Commented

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

Try it 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

J, 49 bytes

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

Try it online!

Will golf further and add explanation tomorrow

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}

Try it online!

How?

• The intersection between a and b contains all elements of b, but in the same order as we would find them in a
  


• So, if we iterate on b and on the intersection in parallel, as soon as we find a difference, we can relocate a single element.


• Relocation is done by cutting a on the position of the element we found in b, then removing the element we found in the intersection, and then adding the remainder of a.


• Repeat from the beginning, until all elements of b are in the right order in a