sciencetalk

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.

Ik snap je vraag niet echt.

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.

slavglot schreef: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 , dat spreek je uit als "42 boven 6".
= 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.

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

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 . 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.

Hier alvast een absolute ondergrens: er zijn drietallen, en binnen een zestal zitten altijd 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.

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.

@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.

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

Binnen een zestal kun je 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.

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

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

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.

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

@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 n_i gebruikt worden, waarbij n_i 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 n₆ is steeds 0 of 1 en indien n₆=1, dan mag het rooster zeker niet toegevoegd worden, dus een "mooie formule" in de n_i kan hierdoor al niet meer volstaan: er moet eerst al zeker minstens één extra voorwaarde komen waaraan een kandidaatrooster moet voldoen.

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.