Springen naar inhoud

Lotto : 3 op 6 correct met minst aantal roosters


  • Log in om te kunnen reageren

#1

slavglot

    slavglot


  • 0 - 25 berichten
  • 5 berichten
  • Gebruiker

Geplaatst op 09 mei 2011 - 22:51

Lotto : welke routine zou mij "random" ALLE combinaties van 6 cijfers kunnen geven om zeker 3 van de 6 juist te hebben met een minimum inzet.

Dit forum kan gratis blijven vanwege banners als deze. Door te registeren zal de onderstaande banner overigens verdwijnen.

#2

Echelon

    Echelon


  • >25 berichten
  • 67 berichten
  • Ervaren gebruiker

Geplaatst op 11 mei 2011 - 17:36

Ik snap je vraag niet echt. ;)

#3

slavglot

    slavglot


  • 0 - 25 berichten
  • 5 berichten
  • Gebruiker

Geplaatst op 14 mei 2011 - 01:06

Lotto : welke routine zou mij "random" ALLE combinaties van 6 cijfers kunnen geven om zeker 3 van de 6 juist te hebben met een minimum inzet.

Hoe bekom ik met zo weinig mogelijk ingevulde roosters (van 1 tot 42) in te
vullen toch dat ik steeds minstens 3 van de 6 getrokken cijfers juist heb?

Bijvoorbeeld : trekking geeft 4-12-13-20-36 en 41.
Als ik 1 rooster invulde met 1-12-13-28-36 en 42 heb ik 3 juist (12,13 en
36) in dit geval.
Maar dit ene rooster geeft nog winst (3 juiste getallen) bij enorm veel
andere combinaties 12-13-1, 12-13-28, 12-13-42,12-36-1, 12-36-13, enz
Dus ik herhaal mijn vraag : hoe bekom ik met zo weinig mogelijk roosters in
te vullen met 6 getallen op een veld van 42 mogelijke getallen zeker 3
getallen juist.
Het berekende aantal roosters interesseert me niet zozeer maar een routine
om al die combinaties van 6 getallen uitgeschreven te krijgen.

De factor "willekeur" dat ik zoek, zit in het feit dat we zowel met de
combinatie 4-12-13-20-36 en 41 als met 1-12-13-28-36 en 42 toch dezelfde 3
getallen 12,13 en 36 juist hebben.

De enige manier die ik me kan inbeelden lijkt door uitschrijven van de 68880
(= 42 x 41 x 40 ) mogelijke 3 getal combinaties op een rooster van 42.
Daaruit willekeurig 2 unieke 3-getal combinaties (bijv. 4-12-13 en 20-36-41)
nemen om een combinatie van 6 getallen te krijgen (in dit vb. 4-12-13-20-36
en 41).
Hieruit de 120 (= 6 x 5 x 4) mogelijke 3 getal-combinaties uitschrijven. En
die schrappen uit de eerste lijst van 68880 combinaties van 3 getallen.
Vervolgens herbeginnen om 2 combinaties van 3 getallen uit de resterende
lijst van 68760 combinaties te kiezen (= 68880 -120)

In het begin werkt dit nog snel : met elke nieuwe combinatie van 6 cijfers
schrapt men 120 combinaties uit de lijst die begon met 68880 combinaties van
3 getallen.

Maar al snel komt men met alsmaar meer gevallen die reeds geschrapt zijn. In
het ene geval eindigen we met veel meer 6 getal-combinaties dan in het
andere geval.

Besluit : er moet een mogelijkheid bestaan om telkens de juiste combinaties
te kiezen (van 2 keer 3 getallen) zodat we zo weinig mogelijk overlap
krijgen.

Ik vermoed dat er ook een wiskundige benadering bestaat waar men helemaal
niet moet schrappen uit 68880 3 getal-combinaties maar direct alle 6
getal-combinaties genereert.die in zich die 68880 3 getal-combinaties bevat.

#4

Rogier

    Rogier


  • >5k berichten
  • 5679 berichten
  • VIP

Geplaatst op 14 mei 2011 - 12:39

Ik vermoed dat er ook een wiskundige benadering bestaat waar men helemaal
niet moet schrappen uit 68880 3 getal-combinaties maar direct alle 6
getal-combinaties genereert.die in zich die 68880 3 getal-combinaties bevat.

Dat heet een combinatie: het aantal mogelijke 6-tallen uit 42 is LaTeX , dat spreek je uit als "42 boven 6".

LaTeX = LaTeX

Het aantal 3-tallen is trouwens niet 68880 maar 11480. Als je alleen 42*41*40 doet, tel je bijvoorbeeld 3-12-17 en 3-17-12 (en zo nog vier andere) als verschillende combinaties.
In theory, there's no difference between theory and practice. In practice, there is.

#5

kee

    kee


  • >250 berichten
  • 389 berichten
  • Ervaren gebruiker

Geplaatst op 14 mei 2011 - 12:51

Moeilijke vraag lijkt me. Het aantal '3-getal-combinaties' is wel 68880/6=11480. De volgorde bij lotto speelt geen rol, het is dus een combinatie.

edit: te laat ;)
edit2 @Rogier: slavglot zoekt niet een formule voor alle '6-getal-combinaties' maar een manier om met zo weinig mogelijk ingevulde roosters alle 3-getal-combinaties te omvatten

Veranderd door kee, 14 mei 2011 - 12:59


#6

kee

    kee


  • >250 berichten
  • 389 berichten
  • Ervaren gebruiker

Geplaatst op 14 mei 2011 - 13:11

Hum, niet helemaal dat wat ik in mijn vorige post zette, de combinaties van 3 getallen moeten niet allemaal omvat worden natuurlijk om zeker drie nummers te hebben.

Bij een trekking van 6 getallen zijn er steeds minstens 3 even of oneven. Je kan dus volstaan met alle combinaties met allemaal even of allemaal oneven getallen te nemen. Dit zijn er LaTeX . Het is dus zeker hoogstens dit aantal.

edit: Negeer maar: Dit ligt dus al hoger dan alle combinaties van 3, dus zeker niet goed. Maar mss kan het wel gecombineerd worden daarmee om tot een antwoord te komen? Dat is dan 2*21*20*19/6 als maximum (gewoon alle te omvatten combinaties van 3, dan al hoogstens de helft daarvan). Of ben ik nu weer op het verkeerde spoor. 'k Zal er eerst eens deftig over nadenken.

Veranderd door kee, 14 mei 2011 - 13:23


#7

Rogier

    Rogier


  • >5k berichten
  • 5679 berichten
  • VIP

Geplaatst op 14 mei 2011 - 14:43

Hier alvast een absolute ondergrens: er zijn LaTeX drietallen, en binnen een zestal zitten altijd LaTeX verschillende drietallen. In het ideale geval zou je dus met 11480/20 = 574 zestallen kunnen volstaan. Maar het lijkt me erg onwaarschijnlijk dat je het geheel zodanig (optimaal) in sets van drietallen kunt verdelen dat je nergens overlap hebt.
In theory, there's no difference between theory and practice. In practice, there is.

#8

slavglot

    slavglot


  • 0 - 25 berichten
  • 5 berichten
  • Gebruiker

Geplaatst op 14 mei 2011 - 23:01

Dat van die 11480 had ik echt over het hoofd gezien.
En effectief komt er na verloop zodanig veel overlap dat wel ver over dat minimum van 574 gaan.
Ik had dit manueel getest met kleinere aantallen te "spelen" in excel.

#9

kee

    kee


  • >250 berichten
  • 389 berichten
  • Ervaren gebruiker

Geplaatst op 15 mei 2011 - 01:39

@Rogier: je 'ondergrens' lijkt me toch eerder een bovengrens dan een ondergrens. Ik heb er nog niet zo heel erg diep over nagedacht maar volgens mij hoef je toch echt niet alle combinaties van 3 getallen te bedekken (zoals in mijn vorige post aangehaald). Ik zie het zo: Stel je hebt een heleboel roosters en elk rooster dat je nu nog kan toevoegen aan de set bevat al een combinatie van 3 getallen die al ergens anders voorkomt in een van de roosters van je set. Dan ben je toch klaar: bij elke trekking van 6 nummers heb je met je set er altijd minstens 3. Als je dus steeds enkel sets toevoegt die hoogstens 2 getallen gemeen hebben met elk van de andere roosters in je set bedek je telkens 20 nieuwe combinaties van 3 getallen, tot op het punt je niets meer kan toevoegen en dan heb je met die set zeker 3 nummers. Op dat moment heb je mogelijks maar niet noodzakelijk alle combinaties van 3 getallen bedekt en heb je dus hoogstens 574 roosters ingevuld. Of zie ik het weer verkeerd?

Om dat concreet uit te voeren lijkt het me een kunstje waar je zot van draait en een programma ervoor schrijven kan ook maar moet telkens dan al die roosters in je set overlopen voor elk mogelijk nieuw rooster en dat lijkt heel moeilijk te programmeren en lang te duren wellicht. En dan heb je nog geen bewijs dat je de efficiŽntste manier van toevoegen hebt. Mss is elke manier even efficiŽnt, maar dat moet je dan toch maar weer bewijzen.

Veranderd door kee, 15 mei 2011 - 01:48


#10

Rogier

    Rogier


  • >5k berichten
  • 5679 berichten
  • VIP

Geplaatst op 15 mei 2011 - 11:12

@Rogier: je 'ondergrens' lijkt me toch eerder een bovengrens dan een ondergrens.

Binnen een zestal kun je LaTeX verschillende drietallen vormen.
Met 574 zestallen kun je dus ten hoogste (in het theoretisch optimale geval met nul overlap) 574*20=11480 verschillende drietallen vormen.

Stel dat je minder dan 574 zestallen hebt. Dan kun je dus minder dan 11480 verschillende drietallen vormen, en aangezien er 11480 mogelijke drietallen zijn (in de verzamling 1..42), zijn er dus drietallen die binnen geen enkele van je zestallen voorkomt. Toch een ondergrens dus.
In theory, there's no difference between theory and practice. In practice, there is.

#11

kee

    kee


  • >250 berichten
  • 389 berichten
  • Ervaren gebruiker

Geplaatst op 15 mei 2011 - 21:41

Doel is toch niet om alle drietallen in je zestallen te hebben maar om met zekerheid drie nummers te hebben ;) .

#12

Rogier

    Rogier


  • >5k berichten
  • 5679 berichten
  • VIP

Geplaatst op 17 mei 2011 - 10:29

Doel is toch niet om alle drietallen in je zestallen te hebben maar om met zekerheid drie nummers te hebben :P .

Heb nu pas je tweede bericht goed gelezen, en inderdaad ;) Best een lastig optimalisatieprobleem, ik zie zo geen formule voor het minimaal benodidge aantal zestallen, laat staan een algoritme om die te genereren.
In theory, there's no difference between theory and practice. In practice, there is.

#13

amai

    amai


  • 0 - 25 berichten
  • 3 berichten
  • Gebruiker

Geplaatst op 29 oktober 2011 - 15:41

hallo,
ik ben nieuw hier en was ook op zoek naar een algoritme om dit te zoeken. Ik heb jaren geleden al eens een programma geschreven om deze combinaties te zoeken. Het werkt wel maar het is van zeer lange duur, volgens mijn berekeningen kan het minstens 50 jaar duren.indien interesse kan ik het wel posten.
groetjes

#14

kee

    kee


  • >250 berichten
  • 389 berichten
  • Ervaren gebruiker

Geplaatst op 04 november 2011 - 13:53

@amai: Voel je vrij om het programma te posten.

Verder: Om de complexiteit van het probleem te illustreren:

Stel dat er maar 12 nummers zijn bij de Lotto in plaats van 42. Het minimum aantal in te vullen roosters om bij elke trekking steeds minstens 3 nummers (=prijs) te hebben is dan 2, bvb de set {{1,2,3,4,5,6},{7,8,9,10,11,12}}. Het mogelijke algoritme voor het toevoegen van de roosters aan de set (zie vorige post van mij) als "Voeg steeds een rooster toe dat hoogstens 2 getallen gemeen heeft met elk van de andere roosters die reeds in de set zitten." is niet streng genoeg om steeds hetzelfde aantal roosters te bekomen in de set voor je niets meer kan toevoegen, bvb kon de set dan in dit geval als volgt starten {{1,2,3,4,5,6},{5,6,7,8,9,10}}, maar dan heb je bvb met {1,2,7,8,11,12} nog geen prijs.

Algemener: stel dat er n nummers zijn in plaats van 42. Het minimum aantal benodigde roosters wordt dan:
n=6: 1
n=7: 1
n=8: 1
n=9: 1
n=10: 2
n=11: 2
n=12: 2
n=13: 2
n=14: vanaf hier wordt het dus moeilijker...

Een eventuele verstrenging van het voorgestelde algoritme zou dan bvb kunnen zijn: "Voeg steeds een rooster toe dat hoogstens 2 getallen gemeen heeft met elk van de andere roosters die reeds in de set zitten en dat met zo weinig mogelijk roosters die reeds in de set zitten 2 getallen gemeen heeft en indien meerdere roosters hieraan voldoen dan een van de roosters die hieraan voldoen en dat met zo weinig mogelijk roosters die reeds in de set zitten precies 1 [of "1 of meer", dat komt hier op hetzelfde neer] getal gemeen heeft."

Of dat werkt moet dan nog bezien worden natuurlijk, en als het niet werkt zijn er ook nog andere mogelijkheden om te verstrengen waar niet meteen logisch is welk het best is, bvb "Voeg steeds een rooster toe dat hoogstens 2 getallen gemeen heeft met elk van de andere roosters die reeds in de set zitten en dat met zo weinig mogelijk roosters die reeds in de set zitten 1 of meer getallen gemeen heeft en indien meerdere roosters hieraan voldoen dan een van de roosters die hieraan voldoen en dat met zo weinig mogelijk roosters die reeds in de set zitten 2 getallen gemeen heeft."

Aan de andere kant is het dan weer niet gezegd dat de eerste vereiste "enkel roosters toevoegen die hoogstens 2 getallen gemeen hebben met andere roosters die reeds in de set zitten" wel optimaal is (hoewel het sterk te betwijfelen valt dat het niet zo zou zijn, maar ik ben er op dit moment niet absoluut zeker van). Algemeen bestaat er misschien een afbeelding dat aan ieder rooster een reŽel getal toekent, waarbij die functiewaarde dan geminimaliseerd moet worden. Een mogelijkheid is dat in het functievoorschrift de variabelen ni gebruikt worden, waarbij ni het aantal roosters uit de set is waarmee een nieuw kandidaatrooster (precies) i getallen gemeen heeft (i=1...6). Echter is of dit werkt wellicht wel te betwijfelen, want n6 is steeds 0 of 1 en indien n6=1, dan mag het rooster zeker niet toegevoegd worden, dus een "mooie formule" in de ni kan hierdoor al niet meer volstaan: er moet eerst al zeker minstens ťťn extra voorwaarde komen waaraan een kandidaatrooster moet voldoen.

Veranderd door kee, 04 november 2011 - 14:05


#15

kee

    kee


  • >250 berichten
  • 389 berichten
  • Ervaren gebruiker

Geplaatst op 04 november 2011 - 15:06

Om verder te gaan: voor een Lotto met 14 getallen heb ik (met de hand) op allerlei mogelijke manieren geprobeerd om met 4 roosters te voldoen (ook door bvb de eerste twee gekozen roosters bewust al voor ťťn getal te laten overlappen, en ook door de 'regel' dat een rooster maar toegevoegd mag worden als het hoogstens 2 getallen gemeen heeft met elk van de andere roosters te negeren), maar er is precies altijd nog een manier om door de mazen van het net te glippen. Dus het lijkt erop: minstens 5 roosters nodig.

Als het niet mogelijk is bij de Lotto met 14 getallen hier een tegenvoorbeeld (met een overlapping in de roosters die op het eerste zicht niet helemaal optimaal is maar uiteindelijk wel werkt) te vinden, sterkt het me echter wel in de overtuiging dat de (op dit moment nog niet exact bekende) regels om een volgend rooster optimaal toe te voegen door het op een of andere manier "zo weinig mogelijk te laten overlappen" wel gaan werken, hoewel dat niet wil zeggen dat er geen andere manieren zijn om op het kleinste aantal roosters uit te komen, maar in de verschillende manieren is er vermoed ik dan altijd een die snel te vinden is door een algoritme te gebruiken dat aan enkele op dit moment niet exact bekende regels voldoet.

Zulke algoritmes doen me denken aan het vierkleurenprobleem, waarvoor ik ooit een eenvoudig algoritme heb opgesteld, ook vertrekkende van een logische basisregel met daarna het verstrengen van het algoritme om voorbeelden waarvoor het niet altijd werkte te omzeilen, heb opgesteld, dat uiteindelijk altijd leek te werken, maar wat ik absoluut niet kon bewijzen.





0 gebruiker(s) lezen dit onderwerp

0 leden, 0 bezoekers, 0 anonieme gebruikers

Ook adverteren op onze website? Lees hier meer!

Gesponsorde vacatures

Vacatures