100 combinaties van 5 getallen (uit de reeks van 1 tot 40). Bijv. 1/7/11/22/38. Hoe kan ik uit al de combinaties de trio's halen die het meest voorkomen?

Antwoord

Dag Albert,

Eigenlijk ben je op zoek naar een efficiënt zoekalgoritme. De eerste mogelijkheid is alle mogelijke trio's opschrijven en dan kijken welke het meeste voorkomen maar dat is natuurlijk veel werk. Want dit betekent in een lijst van 100 keer vijf getallen dat je 1000 trio's met elkaar zal moeten vergelijken.

Dit is eenvoudig uit te rekenen:

Je kan op 10 trio's kiezen uit 5 getallen (wiskundig C(5,3)=10) en dit voor een lijst van 100 rijen betekent dit 1000 trio's.

Eigenlijk kunnen hedendaagse computers makkelijk het meest voorkomende trio kiezen uit 1000 trio's. Waarschijnlijk vraag je je af hoe je dit efficiënter kan aanpakken. Samen met een collega kwamen we met hetvolgende algoritme naar voor.

Stap 1: Neem het meest voorkomende getal uit de lijst van alle getallen, we noemen dit getal eventjes m1. Dit kan een computer (via excel of een andere makkelijk te verkrijgen programma) door een histogram op te stellen en het maximum te bepalen.

Stap 2: Elimineer alle combinaties uit je lijst waar dit getal m1 niet in voorkomt. Dit zal je lijst veel kleiner maken.

Stap 3: Elimineer uit iedere rij van de lijst het getal m1 en start Stap 1 opnieuw.

Als je dit 3 maal uitvoert, vind je een trio (m1,m2,m3).

De vraag is, is dit het meest voorkomende trio?

Niet met 100% zekerheid, maar als je lijst willekeurig getrokken getallen tussen 1 en 40 bevat zal dit het correcte trio opleveren met ongeveer 97% (dit wegens de sterke wet van de grote aantallen). Je mist ongeveer 3% (=1/√1000) omdat het aantal mogelijke trio's eindig is, in jouw geval namelijk 1000. Het zal zeker een veel voorkomend trio zijn maar dus niet noodzakelijk hét meest voorkomende trio (dit slechts in 97% van de gevallen). Als je een tweede vaak voorkomend trio wil vinden elimineer je eerst al de gevonden trio's uit je lijst en je begint het algoritme opnieuw.

Dit algoritme is een statistische oplossing van het probleem. Het is heel snel, toen ik het programmeerde vond mijn computer de 3 meest voorkomende trio's zonder dat ik van mijn koffie kon drinken. Terwijl een brute-force methode en alle trio's met elkaar vergelijken, heel wat langer zal duren.

Hopelijk ben je min of meer tevreden met de statistische aanpak, indien niet dan zal de wiskunde geen antwoord op je vraag kunnen bieden maar zal je de oplossing bij de informatica moeten gaan zoeken.

Groeten,

Kurt.