Множеството подредени списъци се свеждат до един списък, където редът е относителен

Имам множество подредени списъци. За съжаление, редът на елементите не е просто алфа или цифрово сравнение, в противен случай това е тривиално. Така че това, което имам, е нещо като:

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

И от това мога да разбера отколкото мармот ‹ ден на майката, но връзката между мармот и Великден е неизвестна. Гарантирано ми е, че редът на елементите от списък до списък е самопоследователен. (т.е. че без значение в кой списък се среща, Великден винаги е преди Хелоуин)

Но това, от което се нуждая, е нов подреден списък, който представя всеки елемент в другите списъци само веднъж, който запазва всички известни връзки по-горе:

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