Алгоритм сортировки N различных списков из глобального порядка сортировки

Question

У меня есть N списков товаров

Например:

• A, B, C, D
• 1, 2, 3
• V, W, X, Y, Z

Они сведены в один длинный список, и пользователь выбирает порядок по своему вкусу

Например:

1, C, X, 3, B, A, Y, Z, 2, W, D, V

Мне нужно переупорядочить мой N оригиналсписки, поэтому их относительный порядок сортировки совпадает с порядком пользователя

, например:

• C, B, A, D
• 1, 3, 2
• X, Y, Z, W, V

Простой метод грубой силы - создать N новых пустых контейнеров, выполнить цикл заказа пользователя и добавить каждый элемент в соответствующий контейнер при его обнаружении.

Есть либолее элегантный подход?

Answer 1

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

Если вы собираетесь переставить все списки, то более эффективно хранить сведения о том, из какого контейнера поступает каждый элемент, и действовать так, как вы предлагаете.,Если вы собираетесь переставлять только НЕКОТОРЫЕ списки (или переставлять будущие списки), тогда может иметь смысл сохранять сопоставление элемента с позицией в списке и сортировать по нему.Что вы можете сделать либо с помощью функции сравнения, которая проходит через этот поиск, либо с преобразованием Шварца .

Кстати, вы задумывались о том, как обрабатывать повторяющиеся элементы?

Answer 2

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

В какой-то момент вы должны создать каждый из N новых контейнеров.

В какой-то момент вы также должны добавить необходимые элементы в эти контейнеры N.

Этих двух вещей не избежать.В вашем подходе есть и то, и другое, и, следовательно, оно доказано минимальным.

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