Wetenschapsforum

Hallo,

ik ben op zoek naar een formule waarmee ik de positie van een combinatie van getallen kan berekenen binnen een reeks. Ik zal een voorbeeld geven om te verduidelijken:



Ik heb een lijst met alle mogelijke combinaties van drie getallen tussen 1 en 9. In een combinatie kan een getal maar één keer voorkomen (dus geen 113, 552 of 667) en binnen een combinatie zijn de getallen oplopend van links naar rechts (dus 320, 452 etc. komen er niet in voor). Deze lijst ziet er uit als volgt :



begin

1-2-3 positie 1

1-2-4 positie 2

1-2-5 positie 3

1-2-6 positie 4

...

1-2-9 positie 7

1-3-4 positie 8

1-3-5

...

1-3-9

1-4-5

...

...

...

7-8-9

einde



Ik zoek dus een universele formule waarmee ik de positie kan berekenen van een combinatie van n getallen uit het bereik 1 tot m. De formule moet dus ook werken met combinaties van 5 getallen tussen 1 en 20, etc...



Ik ben ervan overtuigd dat dit mogelijk moet zijn, maar zelf ben ik niet in staat om dit op te lossen.





Alvast bedankt,



Blitz.

Het is wel mogelijk, maar het is niet erg zinvol.

Bekijk het eenvoudigste geval met getallenparen

1-2, 1-3, ..., 1-n, 2-3, ..., 2-n, 3-4, ..., (n-1)-n.

Op positie m staat x-y waarbij

x = ceil(n-0,5 - sqrt((n-0,5)^2 - 8*m).

De uitdrukking voor y is nog ingewikkelder.

(ceil betekent: naar boven afronden).

Als je het nodig hebt om iets te programmeren heb je zo'n formule ook helemaal niet nodig.

Ik zoek dus een universele formule waarmee ik de positie kan berekenen van een combinatie van n getallen uit het bereik 1 tot m. De formule moet dus ook werken met combinaties van 5 getallen tussen 1 en 20, etc...

Mag ik weten waarom je dit eigenlijk zoekt, gewoon interesse

Ik heb namelijk een algemene formule/algoritme gevonden (meerdere malen getest en klopte steeds) om de positie te vinden, voor elke lengte van de combinaties en voor elke grootte van het bereik.

Ik zal de stappen toelichten met een voorbeeld. In het voorbeeld loopt het bereik van 1 tot 8 en de combinatie is 4 nummers lang. Het begin van de reeks zal er als volgt uitzien;

1234

1235

1236

1237

1238

1245

…

Nu gaan we bepalen wat de positie wordt van bijvoorbeeld 3568. Het aantal stappen om dit op te lossen is gelijk aan het aantal nummers waaruit de combinatie bestaat. In het voorbeeld dus 4. De stappen houden in dat je kijkt naar het aantal mogelijkheden er zijn tot een bepaalde combinatie. In de stappen moet je steeds dezelfde handelingen verichten, maar steeds met andere waarden.

In stap 1 bekijken we het eerste getal uit het voorbeeld, 3568, dat is het getal 3. De eerste combinatie die mogelijk is met 3 is 3456. Dan gaan we kijken hoeveel combinaties er mogelijk zijn vanaf de eerst mogelijke combinatie 1234 tot 3456.

1234 <aantal combinaties stap1> 3456

In stap 2 bekijken we de eerste twee cijfers uit het voorbeeld (=3568) en zijn 35. De eerste combinatie die mogelijk is met begincijfers 35 is 3567. Dan gaan we kijken hoeveel combinaties er mogelijk zijn vanaf de eerst mogelijke combinatie beginnend met 3 (zie stap1), is 3456 en 3567.

3456 <aantal combinaties stap2> 3567

In de volgende stappen herhaal deze stappen en krijg je;

1234 <stap1> 3456 <stap2> 3567 <stap3> 3567 <stap4> 3568

Om het overzichtelijk te maken moeten de kolommen genummerd worden, van rechts naar links, dus 4321.

Stap 1;

We gaan nu bereken hoeveel combinaties er mogelijk vanaf 1234 (=begin) tot 3456 (=eerst mogelijk getal beginnend met 3).

De formule is;

F = [ 1 / (k+1)!] * [(p+k)! / (p-1)! - (q+k)! / (q-1)!]

s = het verschil van het eerste cijfer uit beide getallen.

s = 3-1 = 2

p = (bereik)-(nummers combinatie)+1 = 5

q = p-s = 3

k = het nummer van het kolom –1 = 3

F = [1/4!]*[8! / 4! – 6! / 2!] = [1/24]*[1680 - 360] = 55

Stap 2;

We gaan nu bereken hoeveel combinaties er mogelijk vanaf 3456 (=eerst mogelijk getal beginnend met 3) tot 3567 (=eerst mogelijk getal beginnend met 35).

s = het verschil van het tweede cijfer uit beide getallen.

s = 5-4 = 1

p = q uit stap hiervoor = 3

q = p-s =3-1 = 2

k = het nummer van het kolom –1 = 2

F = [ 1 / (k+1)!] * [(p+k)! / (p-1)! - (q+k)! / (q-1)!]

F = [1/3!]*[ 5!/2! – 4!/1!] = [1/6 ]*[ 60 – 24 ] = 6

Stap 3;

We gaan nu bereken hoeveel combinaties er mogelijk vanaf 3567 (=eerst mogelijk getal beginnend met 35) tot 3567 (=eerst mogelijk getal beginnend met 356). Hier zie je natuurlijk meteen dat dat nul moet zijn, en dit komt ook uit de formule.

s = het verschil van het derde cijfer uit beide getallen.

s = 0

p = q uit stap hiervoor = 2

q = p-s = 2-0 = 2

k = het nummer van het kolom –1 = 1

F = [ 1 / (k+1)!] * [(p+k)! / (p-1)! - (q+k)! / (q-1)!]

F = [1/2!]*[ 3!/1! – 3!/1!] = [1/2 ]*[ 6 – 6 ] = 0

Stap 4;

We gaan nu bereken hoeveel combinaties er mogelijk vanaf 3567 (=eerst mogelijk getal beginnend met 356) tot 3568 (=het voorbeeld getal). Hier zie je ook meteen wat dat gaat worden, 1 natuurlijk.

s = het verschil van het vierde cijfer uit beide getallen.

s = 1

p = q uit stap hiervoor = 2

q = p-s = 2-1 = 1

k = het nummer van het kolom –1 = 0

F = [ 1 / (k+1)!] * [(p+k)! / (p-1)! - (q+k)! / (q-1)!]

F = [1/1!]*[ 2!/1! – 1!/0!] = [1]*[ 2 – 1 ] = 1

De positie van 3568 is nu als volgt;

Positie = alle stappen optellen +1 = (55+6+0+1) + 1 = 63

Het is op een dergelijke manier ook mogelijk te bepalen hoelang een reeks is. Je doorloopt dezelfde stappen met de laatste combinatie die mogelijk is. Met vier getallen en een bereik van 8 is die combinatie dan 5678