Сортированная комбинация нескольких списков

Question

Рассмотрим L1, L2, L3 как списки, содержащие n1, n2 и n3 целые числа в отсортированном порядке соответственно.

Задача состоит в том, чтобы создать отсортированный список L таким образом, чтобы

L[0] = L1[0] + L2[0] + L3[0]
L[i] = L1[i1] + L2[i2] + L3[i3]
L[n1 * n2 * n3] = L1[n1] + L2[n2] + L3[n3]

Но n1, n2, n3 очень велики, и поэтому L нельзя построить за один раз, а затем отсортировать.

Следовательно, список должен быть построен поэтапно и таким образом, чтобы мы могли отображать k верхних целых чисел и сохранять состояние вычислений для возобновления путем вычисления [k + 1] -го верхнего целого числа.

Какие все структуры данных и алгоритмы могут быть использованы для достижения цели?

Answer 1

Разве вы не можете просто использовать измененную сортировку слиянием , поскольку у вас уже есть три отсортированных списка? (Под «измененным» я подразумеваю то, что использует тот факт, что вы знаете, что каждый входной список уже отсортирован.)

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

Answer 2

ОК, сначала пример в двух измерениях:

    1  2  3

1   2  3  4
5   6  7  8
7   8  9 10

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

Вам понадобится:

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

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

Делаем это с приведенным выше примером: во-первых, список результатов (2). Кандидатами являются ((1 2) 3) и ((2 1) 6). Возьмите кандидата с наименьшим значением, поместите значение в список результатов -> (2 3), найдите координаты всех новых кандидатов -> (2 2) и (1 3), вычислите их значения -> ((2 2) ) 7) и ((1 3) 4), поместите их в кучу кандидатов (сериализованное представление здесь) -> ((1 3) 4) ((2 1) 6) ((2 2) 7), мыльная пена, промыть, повторить.

В табличной форме:

result-list          candidates
(2)                  ((1 2) 3) ((2 1) 6)
(2 3)                ((1 3) 4) ((2 1) 6) ((2 2) 7)
(2 3 4)              ((2 1) 6) ((2 2) 7) ((2 3) 8)
(2 3 4 6)            ((2 2) 7) ((3 1) 8) ((2 3) 8)
(2 3 4 6 7)          ((3 1) 8) ((2 3) 8) ((3 2) 9)
(2 3 4 6 7 8)        ((2 3) 8) ((3 2) 9)
(2 3 4 6 7 8 8)      ((3 2) 9) ((3 3) 10)
(2 3 4 6 7 8 8 9)    ((3 3) 10)
(2 3 4 6 7 8 8 9 10)

Я не вижу лучшего способа в данный момент. Похоже, что для кучи требуется количество узлов по величине суммы n1, n2 и n3.

Answer 3

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

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