Вопросы Теги

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

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

Данный:

  • Перечисляет = {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.

Произведите: список 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; они ненавидят алгоритм (и обычно non-graduate-level математика) вопросы.

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

9
задан Community 23 May 2017 в 11:46
поделиться

5 ответов

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

Это дело, я бы сделал это:

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

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

Проблема в том, что уделяется общему элементу A, нет способа искать его в B в лучшем, чем линейное время (в размере B), потому что все, что у нас есть тест на равенство. Но ясно, что нам нужно как-то найти матчей и (именно там, где я немного волную руки, я не могу немедленно доказать это), поэтому мы должны проверить каждый элемент кондиционеров в 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). Следовательно, объединение ((слияние (a, b), слияние (b, a)) не определено. В целом, выход слияния является произвольным, и если вы ходите с использованием произвольных заказов в качестве основы новых полных заказов, вы будете генерировать взаимно несовместимые заказы.

3
ответ дан 4 December 2019 в 23:06
поделиться

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

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
2
ответ дан 4 December 2019 в 23:06
поделиться

Если элементы усугубляются, это можно сделать в 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)

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

0
ответ дан 4 December 2019 в 23:06
поделиться

будет привязаться к двум спискам достаточно? Это сохраняет относительную сортировку элементов из A и элементов из б.

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

Редактировать: Хорошо, после обсуждения комментариев (и учитывая дополнительное условие, которое a_i = b_i & a_j = b_i & a_i b_i ) Вот разумное решение:

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

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

  3. Создайте список результатов: все элементы A, которые являются перед первым общим элементом, за которым следует все элементы B перед первым общим элементом, за которым следует первый общий элемент, и так далее.

1
ответ дан 4 December 2019 в 23:06
поделиться

Я знаю, что вы уже нашли ответ, но если вы используете размышление, вы увидите хорошую скорость, поскольку GetIdentifier () медленнее. Я писал о том, как сделать метод отражения здесь . Однако это только работает, если вы обращаетесь к вашим собственным ресурсам.

-121--4577884-- 4577884-

Учитывая проблему, поскольку вы выразили ее, у меня ощущение, что проблема не может быть никакого решения. Предположим, что у вас есть две пары элементов {a_1, b_1} и {a_2, b_2} где a_1 в упорядочении 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 может быть «равным« нескольким элементам »или наоборот. Чтобы справиться с ними, алгоритм необходимо проверить каждую b против всех элементов мергенгеля, которые не являются экземплярами B., что делает алгоритм o (n ** 2) в лучший случай.

1
ответ дан 4 December 2019 в 23:06
поделиться
Другие вопросы по тегам:

Похожие вопросы: