Несколько упорядоченных списков сведены к одному списку, где порядок является относительным.

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

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

И из этого я могу понять, чем сурок ‹Mothersday, но связь сурка и пасхи неизвестна. Я гарантирую, что порядок элементов от списка к списку является согласованным. (т.е. независимо от того, в каком списке оно встречается, пасха всегда предшествует Хэллоуину)

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

groundhog
easter
mayday
mothersday
midsummer
laborday
halloween
christmas

Однако следующий список также вполне актуален:

easter
groundhog
mothersday
mayday
midsummer
laborday
halloween
christmas

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

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


c# sorting diff
person Clinton Pierce    schedule 11.11.2008    source источник

Ответы (3)


arrow_upward
5
arrow_downward

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

person bdumitriu    schedule 11.11.2008

arrow_upward
1
arrow_downward

Я согласен с @bdumitriu, вам нужна топологическая сортировка.

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

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

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

--Фил

person Phil    schedule 17.11.2008

arrow_upward
0
arrow_downward

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

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

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

person Paul Sonier    schedule 11.11.2008