Kapalröðun
Úr Wikipediu, frjálsa alfræðiritinu
Kapalröðun er röðunarreiknirit byggt á köplum sem er einkar hentugt til þess að finna lengstu vaxandi hlutrunu.
[breyta] Spilið
Í upphafi er byrjað með stokkaðan spilastokk, spilin númeruð 1,2,...,n. Spilin eru gefin eitt á fætur öðru í hrúgur með eftirfarandi reglum:
- Í upphafi er engin hrúga. Fyrsta spilið myndar fyrstu hrúguna.
- Hvert nýtt spil má ýmist fara á hrúgu sem hefur hærra spil efst (og eykur þannig fjölda spila í þeirri hrúgu), eða í nýja hrúgu til hægri við allar hrúgurnar sem fyrir eru (og eykur þannig fjölda hrúga).
- Spilið endar þegar að öll spilin eru búin af hendi.
Markmið spilsins er að ljúka því með eins fáar hrúgur og hægt er. D. Aldous and P. Diaconis lögðu til að 9 eða færri hrúgur skyldu teljast sigur fyrir n=52, en líkurnar á því eru um það bil 5%.
[breyta] Röðunarreiknirit
Sé gefið n staka fylki með raðvenslum, má líta á það sem safn spila með (enn óþekktu) tölfræðilega röðun hvers staks sem vísi. Í spilinu er aldrei notað raunverulegt gildi spilanna nema við samanburð, og afstæð röðun hverra tveggja staka í fylkinu er vel skilgreind (það er að segja, það er ekki gert ráð fyrir að tvö stök taki sama gildið).
Nú skal spilið spilað, með eigingjörnu aðferðinni, þ.e. að setja spilið alltaf á þá hrúgu sem er lengst til vinstri af þeim sem má setja spilið í. Í hverju skrefi spilsins eru tölugildin vaxandi frá vinstri til hægri. Til þess að heimta raðaða fylkið í lok keyrslu skal taka lægstu spilin af efstu röð þar til að hrúgurnar tæmast.
[breyta] Að finna lengstu vaxandi hlutrunu
Fyrst skal beita röðunarreikniritinu eins og því er lýst að ofan. Fjöldi hrúga er lengd lengstu vaxandi hlutrunu. Þegar spili er komið fyrir efst á hrúgu skal setja bendi frá því að efsta staki hrúgunnar á undan, sem gera má fyrir að hafi haft lægra gildi. Í lokin má rekja sig eftir bendunum til þess að fá lengstu vaxandi hlutrunu í öfugri röð.
