Keskustelu: Ohjelmointikysymykset: Java: Pyydetyn kombinaation generointi

Alkuperäinen kuvaava otsikko oli jotakuinkin: Lottorivien numerointi (unrank ja rank -algoritmit)

Löytyisikö keneltäkään tietoa moisesta algoritmista. Otsikossa nyt lukee lottorivi, mutta kyseessä nyt on algoritmi ihan geneerisesti systeemille jossa valitaan x vaihtoehtoa y:stä mahdollisesta. Lotossahan x=7 ja y=39.

Eli jos lottorivi-esimerkillä mennään niin rivit voisi ajatella esimerkiksi seuraavasti:

1. 1 2 3 4 5 6 7
2. 1 2 3 4 5 6 8
3. 1 2 3 4 5 6 9
...
33. 1 2 3 4 5 6 39
34. 1 2 3 4 5 7 8
35. 1 2 3 4 5 7 9
...
65. 1 2 3 4 5 7 39
66. 1 2 3 4 5 8 9
..
561. 1 2 3 4 5 38 39
562. 1 2 3 4 6 7 8
563. 1 2 3 4 6 7 9
...
15380935. 32 33 35 36 37 38 39
15380936. 32 34 35 36 37 38 39
15380937. 33 34 35 36 37 38 39

Eli periaatteessahan unrank funktio tuollaisille ottaisi sisään esim. järjestysnumero 563 ja antaisi ulos {1,2,3,4,6,7,9} ja rank funktio ottaisi sisään esim {1,2,3,4,5,38,39} ja antaisi ulos 561.

Ongelma vaan, että ei ole käsillä mitään algoritmikirjaa josta löytyisi näppärä ratkaisu tuollaiselle ja ei ihan pienellä pohtimisella tule mieleen eleganttia ratkaisua.

Tarvetta olisi lähinnä tuolle unrank -funktiolle. Järjestyksen ei tarvitse olla sama kuin tuossa edellä esimerkissä esitin, kunhan vaan jokaisella kokonaisluvulla 1 - (y! / x! / (y-x)!) tulee eri rivi - ja tietysti samalla kokonaisluvulla joka kerta sama.

Tällainen ratkaisu löytyi permutaatioille:
http://en.wikipedia.org/wiki/Permutation­#Algorithm_to_generate_permutations
Josko tuosta olisi apua eteenpäinkin.

Edit:
Niin siis erilaisia vaihtoehtoja numeroiden valinnalle on n!/(k!*(n-k)!), lienee helppoa muodostaa luku kuvaamaan, mitkä lottonumerot on valittu. Näillä numeroilla taas on k! mahdollista järjestystä, tässä voisi tuota mainitsemaani algoritmia soveltaa.

P.S. Korjasin otsikkoa mielestäni kuvaavammaksi.

Metabolix kirjoitti:

Tällainen ratkaisu löytyi permutaatioille:
http://en.wikipedia.org/wiki/Permutation­#Algorithm_to_generate_permutations

Ei ole mielestäni apua, koska tuo ei ole mitä hain. Eli siis en tule koskaan haluamaan esimerkiksi numerosarjaa 7, 19, 2, 3, 25, 24, 32.

Mielestäni tuo on aivan väärä lähetysmistapa. Eli jos ajatellaan että käyttäisin tässä jotenkin permutaatiota. Voisin tietysti ottaa kaikki 39 numeroa järjestyksessä, permuotoida ne johonkin n. 2,040*10^46 järjestyksestä, poimia esimerkiksi 7 ensimmäistä numeroa ja järjestää ne. Ongelma tässä vaan on, että sitten pitäisi keksiä, miten generoin luvusta 1-15380937 luvun 1-n. 2,040*10^46 niin, että sieltä ei tule päällekkäisiä rivejä. Veikkaan että tämä ongelma on monta kertaluokkaa vaikeampi kuin alkuperäinen ongelma.

Mutta joo, eli siis kysehän on tässä tapauksessa siis tästä http://en.wikipedia.org/wiki/Combinadic - ehkäpä tuosta löydän sen algoritminkin.

Näköjään löytyi implementaatiokin: http://docs.google.com/View?docid­=ddd8c4hm_5fkdr3b

Metabolix kirjoitti:

Edit:
Niin siis erilaisia vaihtoehtoja numeroiden valinnalle on n!/(k!*(n-k)!), lienee helppoa muodostaa luku kuvaamaan, mitkä lottonumerot on valittu.

Tätä toivoinkin, siis että juuri tämä olisi helppoa.

Metabolix kirjoitti:

Näillä numeroilla taas on k! mahdollista järjestystä, tässä voisi tuota mainitsemaani algoritmia soveltaa.

Tosin minua ei kiinnosta muuta kuin se luonnollinen järjestys. (eli pienin ensimmäisenä, suurin viimeisenä) Eli kun vaan saisin tuon toivomani (permutaatiosta välittämättä) niin voisin kyllä helposti sortata lopputuloksen oikeaksi.

lainaus:

P.S. Korjasin otsikkoa mielestäni kuvaavammaksi.

Mielestäni se on nyt äärettömän paljon epäkuvaavampi.

Minä lähtisin miettimään unrank-funktiota näin: Kun tiedossa on järjestysnumero, ensimmäinen tehtävä on selvittää ensimmäinen lottonumero. Olkoon järjestysnumero 12345678. Sellaisia järjestettyjä rivejä, joissa ensimmäinen numero on 1, on C(38, 6) (ykkösen perään pitää laittaa 6 numeroa sitä suuremmista) eli 38! / (32! * 6!) eli 2760681. Eli kun järjestysnumero on tätä suurempi, ensimmäinen numero ei ole 1. Vastaavasti järjestettyjä rivejä, joissa ensimmäinen numero on 2, on C(37, 6) eli 2324784. Koska 2760681 + 2324784 < 12345678, ensimmäinen numero ei ole myöskään 2. Näin jatketaan, kunnes löytyy oikea ensimmäinen numero. Tämän jälkeen selvitetään muut numerot vastaavasti rekursiivisesti. En nyt miettinyt kaikkia yksityiskohtia, mutta näin sen pitäisi mennä. Funktion rank voi myös luultavasti toteuttaa samalla idealla. Algoritmin miettimistä voisi auttaa sellainen esimerkkitilanne, jossa kaikki kombinaatiot pystyy listaamaan käsin, jotta näkee kunnolla, mitä niissä tapahtuu.

Antti, tuo on mielestäni ihan toimiva yksinkertainen tapa. Tuota mietin itsekin, mutta ajattelin että jos siihen vaikka löytyisi joku ratkaisu jossa ei tarvitse pyöritellä looppeja. Mitä nyt katsoin tuota netistä löytynyttä Java-implementaatiota, niin eipä taida mitään "fiksumpaa" tapaa sinänsä löytyä.

Minusta tuo olisi jo ihan tehokas ja tyylikäs ratkaisu, mutta kerro toki, jos löydät jostain jotain parempaa. Silmukat eivät minua huoleta, kun niissä ei kulu nimeksikään aikaa, mutta tuon C-funktion toteutus on vähän tylsää puuhaa.

Joo, itse asiassa tarpeena oli vaan käydä kaikki rivit läpi ja löytää optimaalisin. Ajattelin että olisi kiva vaan for-loopissa käydä läpi luvut 1-n ja generoida siitä rivi ja tallentaa "parhaan" rivin järjestysnumero muuttujaan. Kuitenkin kun tuo unrank nyt lopulta on sen verran vaikea ja "raskas", niin totesin että nopeampaa ja siistimpää vaan kulkea niitä rivejä eteenpäin ja tallentaa se optimaalinen rivi avattuna taulukkoon.

Rivien läpikäyntifunktiothan on äkkiseltään ajatellen suorastaan järkyttävän yksinkertaiset. (laitan nyt tähän vaikka ei alkuperäiseen kysymykseen suoranaisesti liitykään)

Function FirstRow(Selections As Long, Options As Long) As Long()
    Dim r() As Long
    Static i As Long
    ReDim r(Selections - 1)
    For i = 0 To Selections - 1
        r(i) = i - Selections + Options
    Next
    FirstRow = r
End Function
Function NextRow(row() As Long) As Boolean
    Static p As Long, i As Long, j As Long
    'Palauttaa true mikäli annettu rivi oli viimeinen
    p = 0
    For i = 0 To UBound(row)
        If p < row(i) Then
            row(i) = row(i) - 1
            For j = i - 1 To 0 Step -1
                row(j) = row(j + 1) - 1
            Next
            Exit Function
        Else
            p = row(i) + 1
        End If
    Next
    NextRow = True
End Function

Yksinkertaisuuden vuoksi tuo käy ne läpi eri järjestyksessä alkuperäiseen postiini verrattuna, mutta järjestyksellä ei tosiaan omassa tapauksessani ole mitään väliä.