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

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 не определен для любых действительных и j.
• Оператор равенства =, определенный среди всех элементов A или B (он определяется между элементом из A и элементом из B).
• Нет двух элементов из списка А не равны, и то же самое справедливо и для списка В.

Продукция: список С = {c_1, ..., c_r} таким образом, что:

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

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

Контекст.

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

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

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

Answer 1

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

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

• Возьмите первый элемент А. (оставшееся)
• Посмотрите на него в (то, что осталось) B.
  • Если вы не нашли его в B, переместите его на выход
  • Если вы нашли его в B, переместите все от B до и включите его, а затем отправьте копию с.
• Повторите описанную выше, пока пуст
• Move ничего не осталось в 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 , b, c, 4,5, d, e, f), что мне кажется хорошим. Он выполняет 24 теста на равенство в процессе (если я не могу сосчитать): 6 + 6 + 3 + 3 + 3 + 3. Слияние с A и B будет наоборот (a, b, 1,2, c , d, e, 4,5, f), в этом случае с тем же числом сравнений, поскольку в этом случае совпадающие элементы имеют одинаковые индексы в двух списках.

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

Answer 2

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

EDIT 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

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

Тогда это просто вопрос удаления дубликатов.

EDIT: Хорошо, после того, как комментарий к обсуждению (и данного дополнительного условия, что a_i=b_i & a_j=b_j & a_i<a_j => b_i<b-J), вот разумное решение:

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

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

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

Answer 4

Учитывая проблему, как вы ее выразили, у меня возникает ощущение, что проблема может не иметь решения. Предположим, что у вас есть две пары элементов {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 на все элементы объединенного списка, которые не являются экземплярами B. Это делает алгоритм O(N**2) в лучшем случае.

Answer 5

Если элементы hashable, это может быть сделано в O (N) времени, где N представляет собой общее количество элементов в А и В.

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) 

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