Несколько упорядоченных списков сводятся к одному списку, где порядок является относительным - PullRequest
2 голосов
/ 12 ноября 2008

У меня есть несколько упорядоченных списков. К сожалению, порядок элементов не просто сравнение букв или цифр, в противном случае это тривиально. Так что у меня есть что-то вроде:

List #1        List #2       List #3
groundhog      groundhog     easter
mothersday     mayday        mothersday
midsummer      laborday      halloween
christmas

И из этого я могу понять, чем сурок <день матери, но связь сурка и пасхи неизвестна. Я гарантирую, что порядок элементов из списка в список является самосогласованным. (т.е. независимо от того, в каком списке он встречается, Пасха всегда перед Хэллоуином) </p>

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

groundhog
easter
mayday
mothersday
midsummer
laborday
halloween
christmas

Тем не менее, следующий список также совершенно действителен:

easter
groundhog
mothersday
mayday
midsummer
laborday
halloween
christmas

Я ищу довольно быстрый, универсальный алгоритм, который можно использовать для упорядочения N списков таким образом. (Рабочий код C # плюс, конечно, но не обязательно.)

У меня есть решение, которое работает, но его O (N ^ 2) и собака с даже скромными наборами данных.

Ответы [ 3 ]

5 голосов
/ 12 ноября 2008

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

1 голос
/ 18 ноября 2008

Я согласен с @bdumitriu, вы хотите топологическую сортировку.

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

Топологическая сортировка обычно работает, сначала создавая ориентированный ациклический граф ваших элементов, где каждый элемент становится вершиной, а направленное ребро от узла X к узлу Y означает, что элемент X предшествует элементу Y в ваших входных списках. (Таким образом, вы будете проходить через набор входных отсортированных списков, и каждый раз, когда вы сталкиваетесь с новым элементом, вы создаете для него вершину, и для каждой последовательной пары элементов в каждом отсортированном списке вы делаете направленное ребро из от первого элемента ко второму. Обратите внимание, что вам не нужно создавать направленные ребра от элемента до всех предыдущих элементов в каждом входном списке, например, в вашем входном списке 1, вы должны создать ребра groundhog -> mothersday, mothersday -> midsummer и midsummer -> christmas.)

Топологическая сортировка займет время O (V + E), где V - общее количество сортируемых элементов (количество вершин), а E - общее количество отношений предшественников из ваших входных списков (число краев).

- Phil

0 голосов
/ 12 ноября 2008

Я бы использовал метод Array.Sort с методом сравнения, который берет две сравниваемые строки и затем проверяет их наличие в любом списке; любой список, в котором есть оба, найти их относительные позиции и вернуться на основе этого; если ни в одном списке их нет, вернуть равенство.

В документации MSN говорится, что их алгоритм сортировки использует быструю сортировку; усреднение nlog (n) порядка, в худшем случае порядка n ^ 2.

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

...