Алгоритм объединения двух списков без сравнения между ними

Question

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

Дано:

• Списки A = {a_1, ..., a_m} и B = {b_1, ..., b_n}. (Их также можно считать множествами).
• Оператор приоритета <, определенный среди элементов каждого списка так, что a_i < a_{i+1} и b_j < b_{j+1} для 1 <= i <= m и 1 <= j <= n.
• Оператор приоритета не определен между элементами A и B: a_i < b_j не определен для любых допустимых i и j.
• Оператор равенства =, определенный среди всех элементов A или B (определяется между элементом из A и элементом из B).
• Нет двух элементов из списка A равных, и то же самое относится к списку B.

Produce: Список C = {c_1, ..., c_r} такой, что:

• C = union(A, B); элементы C являются объединением элементов из A и B.
• Если c_p = a_i, c_q = a_j и a_i < a_j, то c_p < c_q. (Порядок элементов из подсписков C, соответствующих множествам A и B., следует сохранить.
• Не существует i и j таких, что c_i = c_j. (все дублированные элементы между A и B удаляются).

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

Контекст:

Конструктивное число может быть представлено точно в конечном числе квадратичных расширений поля рациональных чисел (используя двоичное дерево высоты, равное количеству расширений поля). Следовательно, представление конструктивного числа должно «знать» поле, в котором оно представлено. Списки A и B представляют последовательные квадратичные расширения рациональных чисел. Элементы A и B сами по себе являются конструктивными числами, которые определены в контексте предыдущих меньших полей (следовательно, оператор приоритета). При добавлении / умножении конструктивных чисел, квадратно расширенные поля должны быть сначала объединены так, чтобы двоичная арифметика операции могут быть выполнены; результирующий список C является квадратично расширенным полем, которое может представлять числа, представимые обоими полями A и B. (Если у кого-то есть лучшее представление о том, как программно работать с конструктивными числами, дайте мне знать. Вопрос о конструктивных числах возник , возникший до , а также вот несколько интересных ответов об их представление.)

Прежде чем кто-либо спросит, нет, этот вопрос не относится к mathoverflow; они ненавидят алгоритмические (и, как правило, математические вопросы).

На практике списки A и B являются связанными списками (на самом деле хранятся в обратном порядке). Мне также нужно будет отслеживать, какие элементы C соответствуют, а какие в A и B, но это незначительная деталь. Алгоритм, который я ищу, это не операция слияния в сортировке потому что оператор приоритета не определен между элементами двух списков, которые будут объединены. В конечном итоге все будет реализовано в C ++ (я просто хочу перегрузку операторов). Это не домашнее задание, и в конечном итоге будет открытым исходным кодом, FWIW.

Answer 1

Я не думаю вы можете сделать это лучше, чем O (N * M), хотя я был бы рад ошибаться.

В таком случае, я бы сделал это:

• Возьмите первый (оставшийся) элемент A.
• Ищите это в (что осталось от) Б.
  • Если вы не нашли его в B, переместите его на выход
  • Если вы найдете его в B, переместите все от B до совпадения и включите его и отбросьте копию из A.
• Повторяйте выше, пока A не станет пустым
• Переместить все что осталось в B на выход

Если вы хотите обнаружить несовместимые порядки A и B, то удалите «(то, что осталось от)» из шага 2. Найдите весь B и выведите ошибку, если вы обнаружите, что «слишком рано».

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

Таким образом, в худшем случае пересечение списков является пустым, и никакие элементы A не сравнимы по порядку с любыми элементами B. Для установления требуется N * M тестов на равенство, следовательно, предел наихудшего случая.

Для вашего примера задачи A = (1, 2, c, 4, 5, f), B = (a, b, c, d, e, f), это дает результат (1,2, a, б, в, 4,5, д, е, е), что мне кажется хорошим. Он выполняет 24 теста на равенство в процессе (если я не могу сосчитать): 6 + 6 + 3 + 3 + 3 + 3. Слияние с A и B, наоборот, даст (a, b, 1,2, c , d, e, 4,5, f), в данном случае с одинаковым количеством сравнений, поскольку совпадающие элементы в обоих списках имеют одинаковые индексы.

Как видно из примера, операция не может быть повторена. объединение (A, B) приводит к списку с порядком, несовместимым с порядком слияния (B, A). Следовательно, слияние ((слияние (A, B), слияние (B, A)) не определено. В общем случае результат слияния является произвольным, и если вы будете использовать произвольные порядки в качестве основы для новых полных заказов, вы будете генерировать взаимно несовместимые заказы.

Answer 2

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

РЕДАКТИРОВАТЬ 2:

Теперь с комбинированной рутиной:

import itertools

list1 = [1, 2, 'c', 4, 5, 'f', 7]
list2 = ['a', 'b', 'c', 'd', 'e', 'f', 'g']

ibase = 0
result = []

for n1, i1 in enumerate(list1):
  for n2, i2 in enumerate(itertools.islice(list2, ibase, None, 1)):
    if i1 == i2:
      result.extend(itertools.islice(list2, ibase, ibase + n2))
      result.append(i2)
      ibase = n2 + ibase + 1
      break
  else:
    result.append(i1)
result.extend(itertools.islice(list2, ibase, None, 1))

print result

Answer 3

Учитывая проблему, как вы ее выразили, у меня есть ощущение, что проблема может не иметь решения. Предположим, что у вас есть две пары элементов {a_1, b_1} и {a_2, b_2}, где a_1 < a_2 в порядке A и b_1 > b_2 в порядке B. Теперь предположим, что a_1 = b_1 и a_2 = b_2 в соответствии с оператором равенства для A и B. В этом сценарии я не думаю, что вы можете создать комбинированный список, который удовлетворяет требованию упорядочения подсписков.

Во всяком случае, есть алгоритм, который должен добиться цели. (Закодировано в Java-ish ...)

List<A> alist = ...
List<B> blist = ...
List<Object> mergedList = new SomeList<Object>(alist);
int mergePos = 0;
for (B b : blist) {
    boolean found = false;
    for (int i = mergePos; i < mergedList.size(); i++) {
        if (equals(mergedList.get(i), b)) {
            found = true; break;
        }
    }
    if (!found) {
        mergedList.insertBefore(b, mergePos);
        mergePos++;
    }
}

Этот алгоритм O(N**2) в худшем случае и O(N) в лучшем случае. (Я катаюсь по некоторым деталям реализации Java ... как, например, комбинирование итерации и вставки списка без значительных потерь сложности ... но я думаю, что это можно сделать в этом случае.)

Алгоритм пренебрегает патологией, о которой я говорил в первом абзаце, и другими патологиями; например что элемент B может быть «равен» нескольким элементам A или наоборот. Чтобы справиться с этим, алгоритм должен проверять каждый b по всем элементам mergedList, которые не являются экземплярами B. Это делает алгоритм O(N**2) в лучшем случае.

Answer 4

Будет ли достаточно объединить два списка? Он сохраняет относительную сортировку элементов из a и элементов из b.

Тогда нужно просто удалить дубликаты.

РЕДАКТИРОВАТЬ: Хорошо, после обсуждения комментария (и учитывая дополнительное условие, что a_i=b_i & a_j=b_j & a_i<a_j => b_i<b-J), вот разумное решение:

1. Определение записей, общих для обоих списков. Это O (n ² ) для наивного алгоритма - вы можете улучшить его.

2. (необязательно), убедитесь, что общие записи находятся в одном и том же порядке в обоих списках.

3. Построить список результатов: все элементы a перед первым общим элементом, затем все элементы b перед первым общим элементом, затем первый общий элемент и т. Д. 1021 *

Answer 5

Если элементы являются хэшируемыми, это можно сделать за время O (N), где N - общее количество элементов в A и B.

def merge(A, B):
    # Walk A and build a hash table mapping its values to indices.
    amap = {}
    for i, a in enumerate(A):
        amap[a] = i

    # Now walk B building C.
    C = []
    ai = 0
    bi = 0
    for i, b in enumerate(B):
        if b in amap:
            # b is in both lists.
            new_ai = amap[b]
            assert new_ai >= ai  # check for consistent input
            C += A[ai:new_ai]    # add non-shared elements from A
            C += B[bi:i]         # add non-shared elements from B
            C.append(b)          # add the shared element b
            ai = new_ai + 1
            bi = i + 1
    C += A[ai:]  # add remaining non-shared elements from A
    C += B[bi:]  # from B
    return C

A = [1, 2, 'c', 4, 5, 'f', 7]
B = ['a', 'b', 'c', 'd', 'e', 'f', 'g']
print merge(A, B)

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