Paciencluda ordigo

Paciencluda ordigo (angle patience sorting) estas algoritmo por ordigo, bazita sur karta paciencludo, kio povas efike komputi la plej longan pliiĝantan subsekvencon en donita tabelo.

La kartludo

La ludo komenciĝas de miksita kartaro, markita $1,2,\ldots ,n$.

Iu disdonas la kartojn unu post alia laŭ la sekvencon de aretoj sur la tablo, konforme kun la sube menciitaj reguloj:

1. Komence, estas neniom aretoj. La unua disdonita karto estigas la solan unukartan areton.
2. Ĉiu nova karto povas lokiĝi aŭ sur iun areton havantan pli valoran (ol tiu nova karto) karton ĉe la supro, tiel pliigante la nombron de kartoj en la areto, aŭ dekstre de ĉiuj aretoj, tiel estigante alian novan areton.
3. Kiam oni ne plu havas kartojn en la kartaro, la ludo finiĝas.

La celo de la ludo estas fini kun la plej malgranda nombro de la aretoj. D. Aldous kaj P. Diaconis [1, p.414] proponas difini 9 aŭ malpli aretojn kiel venka rezulto por $n=52$, kio havas ĉirkaŭ 5%-an probablon okazi.

La algoritmo de ordigo

Por iu $n$-era tabelo kaj dezirata rilato de tuteca ordo donitaj kiel enigaĵoj por ordigado, konsideru la tabelon kiel kartaron, kun la (nekonata komence) ordo statistika de ĉiu ero ludanta la rolon de ties indekso por la paciencludo. Rimarku ke la ludo neniam uzas la efektivan valoron de iu karto, krom por komparado kun la valoro de alia karto, kaj la relativa ordo de iuj ajn du tabeleroj estas konata.

Nun imitu la paciencludon, ludante per strategio avida, t.e., lokante ĉiun sekvan karton sur la plej maldekstran areton kiel eble. Tiel ĉiupaŝe, per tiu strategio, la valoroj ĉe la suproj de la aretoj pligrandiĝas, de maldekstro al dekstro. Kiam la kartaro ekelĉerpiĝas, oni povas ekstrakti la orditan sekvencon per preni de la suproj la karton de la plej malgranda valoro, unun post alia.

Priskribo de bonrendimenta realigo de la ordigo, kun funkcia tempo de la plej malbona kazo $O(n\cdot \log \log n)$ ĝis la fino de la lokado de la kartoj en aretojn (t.e., kio faras la plej malbonan kazon de kompleta ordigo de la tabelo $O(n\log n)$), kaj kun spaco $O(n)$ spezita por la helpaj datumstrukturoj (uzante la arbon de van Emde Boas), aperis en artikolo de S. Bespamyatnikh kaj M. Segal [4, pp.7–8].

La algoritmo de komputado de plej longa pliiĝanta subsekvenco

Komence, plenumu la ordigan algoritmon supre priskribitan ĝis la elĉerpo de la kartaro. La rezulta nombro de la aretoj egalos la longon de plej longa pliiĝanta subsekvenco. Dum la algoritmo, kun ĉiu karto metu ankaŭ retromontrilon al la karto tiam ĉe la supro de la antaŭa areto (kies supra karto supozeble malpli valoras la nova karto, laŭ la reguloj de la konstruado de la aretoj). Fine, laŭiru la retromontrilojn ekde la supra karto de la lasta areto, por ekstrakti plej longan malpliiĝantan subsekvencon (de la fino ĝis la komenco); ties renverso estas la celo de la algoritmo por la plej longa pliiĝanta subsekvenco.

S. Bespamyatnikh kaj M. Segal [4, pp.3–5] donis priskribon de altrendimenta realigo de la algoritmo, nepostulante aldonan tempon/spacon asimptote ol la originala algoritmo de la ordigo, ĉar la kreado, la storado, kaj la trairado de la montriloj bezonas nur de lineara tempo/spaco. Ili plu montras ankaŭ kiel ekstrakti ĉiuj plej longajn pliiĝantajn subsekvencojn de samaj rezultantaj datumstrukturoj.

Historio

Laŭ D. Aldous kaj P. Diaconis [1, p.417], paciencludan ordigon kiel algoritmon por komputi la plej longan pliiĝantan subsekvencon unuafoje rekonis Hammersley [2, p.362], kaj A.S.C. Ross, kaj sendepende, kiel ordiga algoritmo, Bob Floyd. Unuan analizon faris Mallows [3].

Citoj

[1] David Aldous and Persi Diaconis. Longest increasing subsequences: from patience sorting to the Baik-Deift-Johansson theorem. Bull. (new series) of the Amer. Math. Society, Volume 36, number 4, pages 413–432

[2] J.M. Hammersley. A few seedlings of research. In Proc. Sixth Berkeley Symp. Math. Statist. and Probability, Volume 1, pages 345–394. University of California Press, 1972. MR 53:9457

[3] C.L. Mallows. Patience sorting. Bull. Inst. Math. Appl., 9:216–224, 1973.

[4] Sergei Bespamyatnikh and Michael Segal. Enumerating Longest Increasing Subsequences and Patience Sorting. Arkivigite je 2005-11-04 per la retarkivo Wayback Machine Pacific Inst. for the Math. Sci. Preprints, PIMS-99-3.