Lottotehtävän algoritmi

Anonyymi

Löysin tällaisen tehtävän Ohjelmointiputkan putkapostista Lottovoitto;

Lotossa oli ennen 39 numeroa, joista valittiin 7. Mikä on pienin määrä lottorivejä siten, että arvottiinpa mikä tahansa 7 numeron rivi, on kyseisellä rivillä ainakin 4 yhteistä numeroa jonkun kyseisen rivikokoelman rivin kanssa.

Olen miettinyt, miten tuollainen ohjelma kannattaisi tehdä. Toistaiseksi pystyn tekemään ohjelman, joka arpoo tietyn määrän rivejä. Mutta onko olemassa nopeaa tapaa tarkistaa rivien validius? Yritin tehdä ohjelman, joka tekee listan kaikista eri riveistä ja tarkistaa ne kaikkien rivien kanssa. Mutta noin 15000000 rivin tarkastaminen 400 rivin kanssa on hidasta. Lisäksi kaikkien rivien generoiminen vie aikaa ja muistia.

Onko siis tapaa tehdä funktio nextRow, joka palauttaisi annetusta lottorivistä seuraavan? Eli nextrow([1,2,3,4,5,6,7])=[1,2,3,4,5,6,8], nextrow([1,2,3,4,5,6,8])=[1,2,3,4,5,6,9] jne, vai miten kannattaisi iteroida kaikki rivit? Vai onko olemassa tapaa, jolla ei tarvitsisi tarkistaa kaikkia 15 miljoonaa riviä, eli joku suppeampi osajoukko riittäisi todistamaan, että nyt valittiin kunnollinen joukko rivejä?

13

1673

    Vastaukset

    Anonyymi (Kirjaudu / Rekisteröidy)
    5000
    • Anonyymi

      Eikös oikea vastaus irtoa suoraan talukkolaskennan kaavalla:

      =KOMBINAATIO(7;4)

      eli 35 varitaatiota.

      • Anonyymi

        Lisätäänpä vielä tapa jolla poimit nuo numerosarjat;

        >>> python3
        >>> from itertools import permutations
        >>> perm = permutations([1, 2, 3, 4, 5, 6, 7], 4)
        >>> for i in list(perm): print(i);

        Eikös se näin mene?


      • Anonyymi
        Anonyymi kirjoitti:

        Lisätäänpä vielä tapa jolla poimit nuo numerosarjat;

        >>> python3
        >>> from itertools import permutations
        >>> perm = permutations([1, 2, 3, 4, 5, 6, 7], 4)
        >>> for i in list(perm): print(i);

        Eikös se näin mene?

        Ehkä tuossa jäi epäselvyyttä lisäävä vaikutelma, kun laitoin oikeaa riviä kuvaamaan numerot 1..7, voit käyttää mitä tahansa muita lukuja noiden tilalla.


    • Anonyymi

      Minusta tuntuu, että yrität ratkaista tuota tarpeettoman monimutkaisesti, mutta kyllä sen varmasti noinkin saa oikein. Kannattaa kuitenkin huomata, että NextRow-funktiota ei kannata tehdä käymään rivejä läpi tuossa järjestyksessä, koska se on paljon työläämpää kuin "normaalissa" suuruusjärjestyksessä läpikäyminen.

      Ensimmäinen rivi on siis 1, 2, 3, 4, 5, 6, 7 ja
      toinen rivi on 1, 2, 3, 4, 5, 6, 8, kuten sinullakin, mutta
      kolmas rivi on 1, 2, 3, 4, 5, 6, 9, ja
      neljäs 1, 2, 3, 4, 5, 6, 10,
      ja niin edelleen, kunnes viimeinen luku on käyty läpi kaikilla vaihtoehdoilla:
      1, 2, 3, 4, 5, 6, 39.
      Sitten toiseksi viimeistä numeroa kasvatetaan yhdellä, ja taas käydään viimeinen numero läpi kaikilla vaihtoehdoilla:
      1, 2, 3, 4, 5, 7, 8
      1, 2, 3, 4, 5, 7, 9
      1, 2, 3, 4, 5, 7, 10,
      ...
      1, 2, 3, 4, 5, 7, 39.
      Ja taas kasvatetaan seuraavaa lukua yhdellä:
      1, 2, 3, 4, 5, 8, 9.
      1, 2, 3, 4, 5, 8, 10
      1, 2, 3, 4, 5, 8, 11
      ...
      1, 2, 3, 4, 5, 8, 39
      Ja taas kasvatetaan seuraavaa lukua yhdellä:
      1, 2, 3, 4, 5, 9, 10
      1, 2, 3, 4, 5, 9, 11
      1, 2, 3, 4, 5, 9, 12.
      ...

      Ja niin edelleen.
      Kun käytät tuota järjestystä, niin NextRow-funktio on paljon helpompi keksiä.

    • Hauska tehtävä. Päivitän sitä sen verran, että otan numeron 40 mukaan, kuten lotossa tehtiin kierroksella 48/2016. Erilaisia rivejä on siis 18643560 kappaletta, kuten Veikkauksen sivuilla (peliohjeet / todennäköisyys) kerrotaan.

      Pienin määrä lottorivejä, à 7 numeroa, että ainakin 4 oikein -tulos (jäljempänä "voitto") osuisi niihin on teoriassa 93. Käytännössä tällaista rivikokoelmaa ei pysty valitsemaan, koska osa mahdollisesti arvottavista riveistä tuottaisi väistämättä useamman voiton. Tämä päällekkäisyys tarkoittaa ylimääräisiä rivejä teoreettisen minimin lisäksi.

      Optimaalisen rivikokoelman löytäminen ei ole suoraviivainen tehtävä enkä usko, että löytyy oikotietä onneen, mutta kokoelmassa täytyy olla yli 200 lottoriviä. Alla hieman alustusta aiheeseen. Arvottavan lisänumeron merkitystä en ole huomioinut.

      Mikä tahansa yksittäinen lottorivi tuottaa voiton 202280 tapauksessa 18643560:sta. Jos kokoelman seuraavalla rivillä ei ole yhteisiä numeroita ensimmäisen kanssa, sekin tuottaa voiton 202280 tapauksessa. Ilman yhteisiä numeroita voidaan laatia vain 5 riviä. Kuudenteen riviin on poimittava mukaan kertaalleen jo käytettyjä numeroita ja jos kahdella rivillä on vain yksi yhteinen numero, riveihin osuu kaksi voittoa 400 tapauksessa. Jos kahdella rivillä on kaksi yhteistä numeroa, riveihin osuu kaksi voittoa 3200 tapauksessa jne.

      Tehtävänä on siis tuon päällekkäisyyden minimointi siten, että jokaisella mahdollisesti arvottavalla rivillä 18643560:sta voittaisi yhden, mutta mahdollisimman pienen määrän voittoja.

      Tehtävään kannattaa valita tehokas ohjelmointikieli koska kuten kirjoitit, tarkistaminen on hidasta. Jos unohdamme assemblerin, C-kieli lienee paras vaihtoehto. Esimerkiksi näin:

      char rivi[7] = {1,2,3,4,5,6,7};
      ...

      for (;;)
      {
      // Tarkista voittaako rivi[]
      ...

      // nextrow
      for (int i=7; rivi[i-1] == 40-7 i;)
      if (--i==0)
      exit(0); // Valmis, kaikki rivit läpikäyty
      for (rivi[i-1] ; i <= 7; rivi[i-1] = rivi[i-2] 1);
      }

      Uloin for-luuppi funktion sisään ja "Tarkista voittaako rivi[]" -kohtaan silmukka, jossa tarkistataan kokoelman rivit. Jos rivi[] ei tuota voittoa yhdenkään kokoelmassa olevan rivin kanssa, kokoelmaan on lisättävä numeroita tai kokonainen rivi siten, että rivi[] tuottaa voiton.

      Kokoelman rivien tarkistaminen kannattaa tehdä taitavasti, koska siitä saattaa tulla ohjelman ylivoimaisesti eniten aikaavievä osuus. Tarvittaessa kerron lisää. Onnea tehtävään!

      • Anonyymi

        Mikä on tehokkain tapa tarkistaa voittaako rivi?


      • Anonyymi
        Anonyymi kirjoitti:

        Mikä on tehokkain tapa tarkistaa voittaako rivi?

        Tämän päivän PC-koneet ovat siksi tehokkaita, että C-kielellä koodattu ohjelma käy esimerkiksi kaikki 18643560 riviä läpi silmänräpäyksessä, oli tarkistustapa mikä tahansa.

        Mutta tehokkain tapa on sellainen, missä kokoelman rivit säilytettään bittimaskeina (uint64_t), samoin esimerkin rivi[]. Testaaminen tapahtuu yksinkertaisesti and-operaattorilla ja laskemalla tuloksen ykkösbitit. Laskeminen on ylivoimaisesti tehokkainta prosessorin POPCNT-käskyllä (ks. __popcnt64() ja vastaavat funktiot), jos prosessorista sellainen löytyy.


      • Anonyymi
        Anonyymi kirjoitti:

        Tämän päivän PC-koneet ovat siksi tehokkaita, että C-kielellä koodattu ohjelma käy esimerkiksi kaikki 18643560 riviä läpi silmänräpäyksessä, oli tarkistustapa mikä tahansa.

        Mutta tehokkain tapa on sellainen, missä kokoelman rivit säilytettään bittimaskeina (uint64_t), samoin esimerkin rivi[]. Testaaminen tapahtuu yksinkertaisesti and-operaattorilla ja laskemalla tuloksen ykkösbitit. Laskeminen on ylivoimaisesti tehokkainta prosessorin POPCNT-käskyllä (ks. __popcnt64() ja vastaavat funktiot), jos prosessorista sellainen löytyy.

        Kyseisiä algoritmejä on ollut 70. vuodasta lähtien! Kato netistä mallia!


    • Anonyymi

      Koodasin aikanaan Amigalla tuontyyppisen softan, ja voitin joka viikko muutamia satasia, mutta mitään isompaa pottia ei tullut. Syy tähän oli, että numerot pääsääntöisesti oli aina oikein, mutta se lisänumerojärjestelmä sotki sitten pakkaa juuri sen verran että mitään isompaa pottia ei omalle kohdalleni osunut.

      Iterointia olisi pitänyt kehittää niin että otetaan huomioon todennäköisyys jokaiselle numerolle sen suhteen että tulisiko kyseeseen lisänumero, vai ns. 'virallinen' numero.

      Empä tuon jälkeen ole kokeillut, mutta kokemusta on, ja aika positiivistakin suoraan sanottuna.

      Tulipahan ainakin todistettua että toimii, ja että mahdollista tämä on.

      • Anonyymi

        Amigan aikoihin rivit piti ehkä jättää paperiselle kupongille rastitettuina. Taisi olla hikinen urakka. Nykyään on helpompaa, kun rivit voi rastittaa netissä.

        Lisänumerot eivät sotke tällaista järjestelmää. Varsinkaan, kun nykylotossa arvotaan vain yksi lisänumero ja ainoa voittoluokka, johon se käytännössä vaikuttaa on 6 1 oikein. 3 1 tuloksen voitto on yhtä tyhjän kanssa, joten ei ole väärin lukea pienimmäksi voitoksi 4 oikein tulos.

        Tässä tarkoitettu järjestelmä on käytännössä järjetön siksi koska nykylotossa pienimpien voittojen euromäärät ovat kuihtuneet käytännösä olemattomiksi. Edellä on kerrottu, että rivien optimimäärä olisi 93 ja käytännössä yli 200. Järjestelmän hinnaksi tulisi siis ainakin 200 euroa ja se takaisi vain 4-oikein tuloksen, jolla voittaa 10 euroa!

        Ohjelmointitehtävänä silti mielenkiintoinen ja vaativakin Laitahan Amiga-koodisi näytille...


      • Anonyymi

        "voitin joka viikko muutamia satasia"
        Höpö höpö.


      • Anonyymi
        Anonyymi kirjoitti:

        "voitin joka viikko muutamia satasia"
        Höpö höpö.

        Lotossa ei ole mitään mahdollisuutta kehittää mitään järkevää järjestelmää joka toisi enemmän voittoja. Kaikki perustuu satunnaisuuteen.


      • Anonyymi
        Anonyymi kirjoitti:

        Lotossa ei ole mitään mahdollisuutta kehittää mitään järkevää järjestelmää joka toisi enemmän voittoja. Kaikki perustuu satunnaisuuteen.

        Lotto perustuu satunnaisuuteen, olet oikeassa. Mutta olet väärässä siinä, etteikö järkevällä järjestelmällä voisi vaikuttaa voittojen määrään.

        Tunnetuin esimerkki voittojen määrään vaikuttamisesta lienee kautta aikain yleisimmän rivin lottoaminen. Jos rastitat numerot 1, 2, 3, 4, 5, 6 ja 7 ja voitat, joudut tiettävästi jakamaan (5 oikein tai paremman) voittoluokan voiton poikkeuksellisen suuren pelaajajoukon kanssa.

        Toinen esimerkki on ero järjestelmä- ja haravapelien välillä. Järjestelmä takaa osumien määrää vastaavan voiton ja tuo suuren määrän pienempiä voittoja. Harava takaa vain 4- ja 5-oikein tuloksen, mutta huomattavasti pienemmällä kustannuksella. Toki voiton todennäköisyys sijoitettua euroa kohden on kummassakin pelissä sama. Vastaavasti ruletissa voi asettaa panoksensa yhdelle numerolle (1:30) tai esim. kolmelle (1:10).

        Tämän ketjun aloittaja haki siis haravaa, joka antaisi varman voiton joka kerta. Sellaisessa olisi hyvinkin järkeä mm. lottoporukoiden peli-innon ylläpitäjänä. Tuskin mikään on lannistavampaa kuin pelata viikosta toiseen lottoporukassa, joka ei koskaan voita mitään.

        Keskustelemme ohjelmoinnista ja sen suhteen järjestelmän pohtimisessa on järkeä, mitä Veikkauksen lotossa ei juuri ole.


    Ketjusta on poistettu 0 sääntöjenvastaista viestiä.

    Luetuimmat keskustelut

    1. Nurmossa kuoli 2 Lasta..

      Autokolarissa. Näin kertovat iltapäivälehdet juuri nyt. 22.11. Ja aina ennen Joulua näitä tulee. . .
      Seinäjoki
      131
      7105
    2. Maisa on SALAKUVATTU huumepoliisinsa kanssa!

      https://www.seiska.fi/vain-seiskassa/ensimmainen-yhteiskuva-maisa-torpan-ja-poliisikullan-lahiorakkaus-roihuaa/1525663
      Kotimaiset julkkisjuorut
      165
      4350
    3. Vanhalle ukon rähjälle

      Satutit mua niin paljon kun erottiin. Oletko todella niin itsekäs että kuvittelet että huolisin sut kaiken tapahtuneen
      Ikävä
      54
      3442
    4. Mikko Koivu yrittää pestä mustan valkoiseksi

      Ilmeisesti huomannut, että Helenan tukijoukot kasvaa kasvamistaan. Riistakamera paljasti hiljattain kylmän totuuden Mi
      Kotimaiset julkkisjuorut
      493
      3096
    5. Purra hermostui A-studiossa

      Purra huusi ja tärisi A-studiossa 21.11.-24. Ei kykene asialliseen keskusteluun.
      Perussuomalaiset
      293
      2070
    6. Joel Harkimo seuraa Martina Aitolehden jalanjälkiä!

      Oho, aikamoinen yllätys, että Joel Jolle Harkimo on lähtenyt Iholla-ohjelmaan. Tässähän hän seuraa mm. Martina Aitolehde
      Suomalaiset julkkikset
      36
      1733
    7. Kaksi lasta kuoli kolarissa Seinäjoella. Tutkitaan rikoksena

      Henkilöautossa matkustaneet kaksi lasta ovat kuolleet kolarissa Seinäjoella. Kolmas lapsi on vakasti loukkaantunut ja
      Maailman menoa
      20
      1651
    8. Miten meinasit

      Suhtautua minuun kun taas kohdataan?
      Ikävä
      91
      1563
    9. Miksi pankkitunnuksilla kaikkialle

      Miksi rahaliikenteen palveluiden tunnukset vaaditaan miltei kaikkeen yleiseen asiointiin Suomessa? Kenen etu on se, että
      Maailman menoa
      176
      1472
    10. Ensitreffit Hai rehellisenä - Tämä intiimiyden muoto puuttui suhteesta Annan kanssa: "Meillä ei..."

      Hai ja Anna eivät jatkaneet avioliittoaan Ensitreffit-sarjassa. Olisiko mielestäsi tällä parilla ollut mahdollisuus aito
      Ensitreffit alttarilla
      15
      1426
    Aihe