Выравнивание перекрытия упорядоченных и неупорядоченных списков - PullRequest
Новая
       5

Выравнивание перекрытия упорядоченных и неупорядоченных списков

0 голосов
/ 26 января 2011

Я ищу алгоритм, который может находить / назначать порядок и перекрываться, учитывая список упорядоченных элементов и список неупорядоченных элементов. (из которых перекрытие может существовать или не существовать).

В этом примере я буду использовать целые числа, но они также могут быть именами людей, идентификационными кодами и т. Д. То есть число не может быть использовано для решения реальной проблемы, но для объяснения проблемы я использовал упорядоченный набор (1,2,3,4,5,6,7,8,9,10) как ответ Святого Грааля.

Введите:

Упорядоченный список списков: (1,2,3,4), (8,9,10), (3,4,5)

Неупорядоченный список списков: (3,4,2), (6,4,5,7), (10,9)

Мысленный процесс, как я делаю этот алгоритм в моей голове:

  1. списки 3,4,5 и 1,2,3,4 упорядочены и имеют 3,4 общих, поэтому 2 упорядоченных списка пересекаются, образуя: 1,2,3,4,5 в этом порядке.
  2. Неупорядоченный список 3,4,2 является подмножеством упорядоченного списка 1,2,3,4,5, поэтому его можно изменить на 2,3,4 и сказать, что он перекрывает упорядоченный список 1,2,3, 4,5
  3. Та же идея (как в шаге 2) для упорядоченного списка 8,9,10 по сравнению с неупорядоченным 10,9. Это должно быть 9,10 с 8,9,10.
  4. Теперь сравнивая упорядоченный список 1,2,3,4,5 и неупорядоченный 6,4,5,7, они имеют набор пересечений 4,5, поэтому можно сделать вывод, что его 1,2,3,4,5 , (6,7 | 7,6) где (6,7 | 7,6) означает, что либо 6, либо 7, либо 7, а затем 6 (но неизвестно, что верно)

Выход:

  • Я хотел бы иметь возможность проанализировать матрицу / дерево / любую структуру данных, чтобы увидеть, что перекрывается, где и в каком порядке
  • и сводный список, содержащий наборы частично известного порядка
    • set1: 1,2,3,4,5, (6,7 | 7,6)
    • set2: 2: 8,9,10

Кто-нибудь знает похожую проблему или алгоритм, который я мог бы использовать? В идеале это было бы на Perl, но псевдокод или алгоритмы на другом языке были бы хороши.

Спасибо

1 Ответ

0 голосов
/ 29 января 2011

Если я правильно понимаю, вам нужен один упорядоченный список из набора упорядоченных и неупорядоченных списков. Возможным решением было бы перебрать все значения во всех наборах и добавить их в структуру хэш-таблицы. В терминах реализации это может быть карта C ++, Java HashMap, словарь Python и т. Д. Это будет выглядеть так:

для i на всех множествах S // (Упорядочено и Unordered) 

  for j over all values in S[i]

      H.insert(S[i][j]) //H is the hash table

Теперь перебираем записи в хеш-таблице, чтобы получить требуемый упорядоченный список. Это довольно практично и оптимально.

Не очень практичное решение, но заслуживающее упоминания за его изящество следующее:

  1. Назначьте каждому уникальному номеру соответствующее простое число. Например, в вашем примере, сопоставьте числа следующим образом: p [1] = 2, p [2] = 3, p [3] = 5, p [4] = 7, p [5] = 11, p [6] = 13, p [7] = 17, p [8] = 19, р [9] = 23, р [10] = 29;

  2. Теперь каждый набор Si может быть представлен значением Vi - произведением соответствующих простых чисел. Таким образом, множество Si = (1,2,3) (или в этом отношении (2,1,3)) будет иметь значение Vi = p [1] * p [2] * p [3]

  3. Найдите LCM всех Vi. Назовите это V. V = Для всех я LCM {Vi}

  4. Разложить V на основные факторы. Каждое простое число представляет элемент в вашем окончательном упорядоченном списке.

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

Надеюсь, что хотя бы одна из этих работ для вас!

...