Недавно мне пришлось решить проблему на работе, где у меня было два списка: основной список и меньший список, который содержит подмножество элементов в основном списке, потенциально в другом порядке. Мне нужно было изменить порядок главного списка таким образом, чтобы элементы в подмножестве отображались в том же порядке, не меняя порядок элементов, не найденных в списке, и сохраняя элементы в том же месте, когда это было возможно. Ладно, это может звучать странно, поэтому я разобью это:

• Основной список определяет порядок элементов по умолчанию.
• Список подмножеств определяет относительный порядок определенных элементов.
• Если основной список имеет два элемента не по порядку в соответствии со списком подмножеств, элемент, находящийся ранее в основном списке, должен быть перемещен в самый ранний индекс, где он находится в правильном положении относительно других элементов в списке подмножеств. (т.е. сразу после более позднего пункта)

Ваша задача - реализовать этот алгоритм переупорядочения.

Примеры тестовых случаев

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]

правила

• Стандартные лазейки, Ядда Ядда, удобный ввод-вывод, бла-бла.
• Несмотря на то, что в примерах используются числа и строки, вам нужно поддерживать только один тип элемента, будь то целые числа, строки или что-то еще с четко определенной семантикой равенства, включая гетерогенные списки, если это удобно на вашем языке.
• Вы можете предположить, что и главный список, и список подмножеств не содержат дубликатов
• Вы можете предположить, что все элементы, найденные в списке подмножеств, находятся в основном списке
• Любой список может быть пустым
• Вы должны, как минимум, поддерживать массивы длиной до 100 элементов.
• Переупорядочение может быть реализовано на месте или путем создания нового списка / массива.

Счастливого гольфа!

Сетчатка 0.8.2 , 51 байт

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

Попробуйте онлайн! Принимает ввод как разделенный запятыми список подслов в первой строке и разделенный запятыми основной список слов во второй строке. Объяснение:

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

Найдите два смежных подслов, где второе слово предшествует первому в главном списке.

$1$4,$3

Переместите второе слово, чтобы оно появилось после первого слова в основном списке.

+`

Повторяйте, пока слова не появятся не по порядку.

1A`

Удалить подслов.

JavaScript (ES6),  96 89 74  71 байт

Это началось как громоздкий беспорядок и в конечном итоге сократилось до довольно лаконичной и элегантной формы. Я хотел бы поблагодарить .splice () за его плодотворное сотрудничество. ;)

Принимает вход как (master)(subset). Выходы путем обновления основного списка.

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

Попробуйте онлайн!

Как?

$i$$p$

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

$1$

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

$0$

• внутренний. splice () ничего не удаляет и возвращает пустой массив
• в результате внешний .splice () получает неопределенный в качестве третьего аргумента и ничего не вставляется

комментарии

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 байтов

(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

Попробуйте онлайн!

(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

Рубин , 73 68 байт

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

Попробуйте онлайн!

Как?

• Пересечение aи bсодержит все элементыb , но в том порядке, в котором мы их нашли быa
• Таким образом, если мы bвыполняем параллельное пересечение и пересечение, как только мы находим различие, мы можем переместить один элемент.
• Перемещение выполняется путем вырезания aпозиции элемента, который мы нашли вb , затем удаления элемента, который мы нашли в пересечении, и затем добавления остатка от a.
• Повторите с начала, пока все элементы не bбудут в правильном порядке вa

Python 2 , 124 109 106 99 96 байт

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

Попробуйте онлайн!

Perl 6 , 40 байт

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

Попробуйте онлайн!

Блок анонимного кода, который принимает ввод карри (например, f(subList)(masterList) , и находит первую лексографическую перестановку индексов основного списка, где элементы из подсписка расположены в правильном порядке.

Интуитивно понятно, что первая удовлетворительная перестановка оставит правильно упорядоченные элементы в исходном порядке, в то время как неправильно расположенные элементы будут перемещены на минимально необходимое расстояние вперед, чтобы расположить их в правильном порядке, что позволит разместить их непосредственно после предыдущего элемента в подмножестве.

Объяснение:

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

Желе , 9 байт

Œ!iⱮṢƑ¥ƇḢ

Попробуйте онлайн! или тестовый набор

Неэффективно, особенно с большими списками мастеров. Создает все возможные перестановки, отфильтровывает те, где подмножество находится в неправильном порядке, а затем возвращает первое.

объяснение

Œ!        | 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 байт

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

Попробуйте онлайн!

объяснение

Мы принимаем подмножество в качестве левого аргумента, а полный ввод - в качестве правого.

Мы проработаем код с конкретным примером для ясности:

5 2 4 f 1 2 3 4 5

Возьмите штучные инфиксы второго размера из подмножества:

2 <\ [

производство:

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

добавьте их к исходному вводу и полностью измените

] |.@;

Мы получаем:

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

Решение проблемы становится справа налево сокращение выше. Нам нужно только найти правильный глагол, чтобы вставить/ между элементами.

Каждая итерация сокращения обновляет крайний правый блок (полный ввод, который мы преобразуем), чтобы он соответствовал ограничению порядка, представленному парой слева. Когда сокращение будет завершено, вход будет соответствовать полному порядку подмножества.

Если упорядочение пары совпадает с упорядочением на входе, следующее будет иметь значение 0, и мы ничего не будем делать:

^:(>/@i.~)

В противном случае он будет равен 1, и мы применим глагол слева от ^:

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

который перемещает левый элемент вправо от правого элемента. Это движение просто циклическая перестановка всех элементов между (и включая) двумя этими элементами.

J имеет примитив для применения такой циклической перестановки:

<cyclic permutation definition> C. ]

и остаток от глагола ничего не делает, кроме как выбирает индексы, которые нам нужны для циклического цикла:

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

что кажется длиннее, чем должно быть, но я не смог продвинуть эту фразу дальше.

Наконец мы перезагружаем результат <@и все готово.

Желе , 24 байта

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

Попробуйте онлайн! или тестовый набор

объяснение

Диадическая ссылка, которая принимает подмножество в качестве левого, а основной список - в качестве правого аргумента. В приведенном ниже примере 9001, 42, 69, 1337, 420, 99, 255 в качестве главного и 69, 9001, 1337 в качестве подмножества.

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 #) , 118 байт

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

Попробуйте онлайн!

Использование некоторых классов в System.Collections.Genericпространстве имен. Мастер - это, List<T>а подмножество - 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);
    }
}