VBA voor smarties: Combinaties

Combinaties

1. Combinaties

2. Kenmerken van combinaties

3. Voorbeeldbestand

3.1 Werkblad 'explanation'
3.2 Werkblad 'VBA'
3.3 Werkblad 'VBA-recursie'
3.4 Werkblad 'VBA fixed'
3.5 Werkblad 'formulae'
3.6 Werkblad 'formula_fixed'

1. Combinaties

Geregeld komt in fora de vraag voor naar het aantal mogelijke combinaties van x elementen uit een totaal van n elementen.

2 Kenmerken van combinaties

Combinaties hebben 2 kenmerken:
- in iedere combinatie komt een element slechts één keer voor
- de volgorde van elementen doet er niet toe: ABC is als combinatie gelijk aan ACB, BAC, BCA, CAB , en CBA.

Voorbeeld

Hoeveel combinaties van 5 elementen zijn er in een groep van 10 elementen.

In feite is dit een vraag over een teller in een 10-tallig stelsel.
Een 10-tallig stelsel bevat de elementen 0, 1, 2, 3, 4, 5, 6, 7, 8 en 9.
Alle getallen vanaf 00000 t/m 99999 vormen de verzameling van alle groepen met 5 elementen uit de 10-elementen van het 10-tallig stelsel.
Omdat ieder element in een combinatie maar 1 keer mag voorkomen, is de kleinste groep van 5 elementen 01234.
De grootste groep is dan 56789.
Als we van 01234 tot 56789 tellen hebben we alle groepen van 5 elementen te pakken.
Het aantal combinaties van 5 elementen is veel kleiner dan het aantal groepen van 5 elementen.
Uit het totaal aantal groepen van 5 elementen kunnen we combinaties selecteren door een toetscriterium in te voeren:
- het tweede element moet groter zijn dan het eerste element,
- het derde element moet groter zijn dan het tweede,
- het vierde groter dan het derde en
- het vijfde groter dan het vierde.

Kort geformuleerd:

element 1 < element 2 < element 3 < element 4 < element 5

Als we nu alle getallen tussen 012345 en 56789 genereren en de getallen selecteren die voldoen aan dit criterium zijn we klaar.

In VBA:

For j= 1234 to 56789

c00= format(j,"00000")
if left(c00,1) < mid(c00,2,1) and mid(c00,2,1) < mid(c00,3,1) and mid(c00,3,1) < mid(c00,4,1) and mid(c00,4,1) < right(c00,1) then c01=c01 & vblf & c00

next

msgbox mid(c01,2)

Patroonanalyse

Als we nu naar het patroon kijken in de getallenreeks van 01234 tot 56789 valt op, dat

- als de teller steeds met 1 verhoogd wordt in het meest rechter cijfer van de reeks 01234 we de volgende combinaties krijgen:

01234
01235
01236
01237
01238
01239

- als het hoogste nummer (9) wordt bereikt, krijgt het voorlaatste cijfer er 1 bij (net zoals in het 10-tallig stelsel)

0124..

In de laatste positie beginnen we vervolgens niet met 0, zoals in het 10-tallig stelsel, maar met het nummer volgend op het voorlaatste nummer.
We hanteren nl. als voorwaarde dat het latere element groter moet zijn dan het voorafgaande element.
De eerste combinatie die daaraan voldoet is:

01245

- daarna wordt de laatste teller weer steeds met 1 verhoogd totdat het hoogste nummer (9) wordt bereikt.

De maximale combinatie is 56789.
Hieraan kunnen we zien wat het maximumgetal is per positie:

5e positie: maximum 9
4e positie: maximum 8
3e positie: maximum 7
2e positie: maximum 6
1e positie: maximum 5

Dat betekent dat de teller per positie bij het bereiken van het maximum zorgt voor het verhogen van het getal in de positie ervoor

3. Voorbeeldbestand

Het bijgevoegde voorbeeldbestand bevat 6 werkbladen
- waarin het rotatie-principe grafisch wordt gedemonstreerd
- met flexibele en niet-flexibele VBA-benaderingen
- met flexibele en niet-flexibele benaderingen met Excel-formules

3.1 Werkblad 'explanation'

Het algoritme wordt geïllustreerd aan de hand van alle combinaties van 5 elementen uit een groep van 10 elementen.

Met de knop 'Step 1' kun je iedere fase van het ontstaan van geldige combinaties volgen.
Iedere druk op de knop maakt een nieuwe combinatie.
Een combinatie wordt in de het gebied A1:E252 weggeschreven.

Als grafisch hulpmiddel dienen 5 'klokken' met 10 elementen.
Deze draaien per klik op de knop 'Step 1' kloksgewijs.
De rode cijfers van de klokken komen in de overeenkomende kolom van gebied A1:E252.
Klok V draait het snelst net zoals in een 10-tallig stelsel de eenheden, vervolgens de tientallen, de honderdtallen, etc.
Ook in dit geval lees je het resultaat van iedere klik van rechts naar links.

Wil je opnieuw beginnen, klik dan op knop 'Reset'.
Het gebied A1:E252 wordt gewist.
De klokken worden allemaal op 0 gezet.

Iedere klik start de macro M_rotatie.
Deze macro laat de 5 klokken 'draaien' volgens het bovenbeschreven algoritme.

3.2 Werkblad 'VBA'

Geef in cel B1 het aantal elementen aan, waaruit combinaties gemaakt moeten worden
Geef in cel B2 aan uit hoeveel elementen een combinatie moet bestaan.
Een combinatie kan nooit groter zijn dan het aantal elementen in de populatie.
Cel B3 berekent hoeveel combinaties er mogelijk zijn met de parameters in B1 en B2
Als cel B1 gevuld is en cel B2 een waarde krijgt start de macro M_snb, die de combinaties maakt.

Geef in cel B4 met dubbelklik aan of de combinaties moeten bestaan uit cijfers of uit de labels uit de tabel in gebied A7:A32.
Schakel met dubbelklikken in cel B4 tussen cijfer/label-weergave.

Het resultaat van alle combinaties wordt getoond vanaf cel D1.

Houd er rekening mee dat het aantal combinaties snel groter kan zijn dan het aantal rijen in een Excel werkblad.
In zo'n geval wordt de macro niet uitgevoerd.

In werkblad 'formulae' staat een 30 x 30 tabel in gebied AT1:BX31 waarin het aantal combinaties van x elementen uit y elementen staat aangegeven.
Het hoogste aantal combinaties per populatiegrootte is lichtrood gemarkeerd.
Alle combinatie-aantallen die groter zijn dan het aantal rijen van een Excel-werkblad zijn grijs gemarkeerd.

Macro M_snb

De macro is geoptimaliseerd voor het doorlopen van loops.
De omvang van de 2-dimensionele array waarin de resultaten terecht moet komen is bepalend.
Het aantal combinaties is het aantal 'rijen' van de array; het aantal elementen van een combinatie vormt de tweede dimensie ('kolommen') van de array.

Behalve het aantal rijen van een werkblad kent de macro geen beperkingen.

Het gebruik van een macro zorgt ervoor dat de omvang van het bestand beperkt blijft vergeleken met het gebruik van Excel-formules.
Alle berekeningen worden in het werkgeheugen uitgevoerd.
De rekentijd is verwaarloosbaar vergeleken met het gebruik van Excel-formules.
De interaktie met het werkblad is geminimaliseerd: 1 keer worden gegevens uit het werkblad gelezen; het resultaat wordt in 1 schrijfaktie in het werkblad opgeslagen.

Macro M_snb_000

Deze macro volgt heel precies het bovenbeschreven algoritme.
De macro heeft afzonderlijke code voor:

- de eerste combinatie
- de eerste positie in iedere combinatie
- de laatste positie in iedere combinatie
- de posities tussen de eerste en laatste positie in een combinatie

Als je deze macro met F8 in de VBeditor stap-voor-stap doorloopt zie je dat

- de eerste combinatie alle 'kolomnummers' van de array krijgt
- de eerste positie gelijk is aan de eerste postie van de voorafgaande combinatie, tenzij de tweede positie het maximum van die positie heeft bereikt.
In dat geval wordt er bij de eerste positie 1 opgeteld.
- de laatste positie is de laatste positie van de voorgaande combinatie +1, tenzij het maximum van de laatste positie is bereikt.
In dat geval wordt bij het getal van de voorgaande positie 1 opgeteld.
- een positie krijgt het nummer van de overeenkomstige positie in de voorafgaande combinatie

o tenzij het nummer van de overereenkomstige positie in de voorafgaande combinatie het maximum van die positie bevat; dan krijgt de positie de waarde van de voorafgaande positie van de huidige combinatie +1
o tenzij de volgende positie in de voorafgaande combinatie het maximum van die positie bevat; bij de huidige positie wordt dan 1 opgeteld

De macro is een letterlijke VBA-vertaling van de formules in gebied D2:H252 van het werkblad 'formula_fixed'.

3.3 Werkblad 'VBA-recursie'

Omdat het vraagstuk van combinaties zich uitstekend leent voor het gebruik van recursie, komt dat in een apart werkblad aan de orde.

Geef in cel B1 het aantal elementen aan, waaruit combinaties gemaakt moeten worden
Geef in cel B2 aan uit hoeveel elementen een combinatie bestaat.
Een combinatie kan nooit groter zijn dan het aantal elementen in de populatie.
Cel B3 geeft het aantal mogelijke combinaties met de parameters in B1 en B2
De macro start als cel B1 gevuld is en cel B2 een waarde krijgt.

Geef in cel B4 met dubbelklik aan of de combinaties moeten bestaan uit cijfers of uit de labels uit de tabel in gebied A7:A32.
Dubbelklikken in cel B4 schakelt tussen cijfer/label-weergave.

Het resultaat van alle combinaties komt in cel D1 en volgende.

Macro M_snb

Leest gegevens uit het werkblad.
Maakt een lege array om de resultaten op te slaan
Roept de recursiemacro M_comb aan
Schrijft de resultaten in het werkblad.

Macro M_comb(c00, y, t, v)

Produceert de combinaties door zichzelf aan te roepen.
Schrijft iedere combinatie met het aangegeven aantal elementen in de array
Houdt de voortgang van de productie bij via een teller.

Omdat beide macro's gebruik maken van de ingelezen gegevens in Array sn en de recursiemacro gebruik maakt van de resultaten Array sp, dienen beide als 'Private Scope' (beschikbaar voor de gehele macromodule) gedeclareerd te worden.

De macro is optimaal flexibel: hij funktioneert ongeacht de parameters in B1 en B2
De enige beperking is het aantal rijen van een Excel-werkblad.
Alle berekeningen vinden plaats in het werkgeheugen.
De omvang van de VBA-code is minimaal.
De interaktie met het werkblad is minimaal: 1 x lezen, 1 x schrijven.

De snelheid van de macro is verwaarloosbaar vergeleken met het gebruik van Excel-formules.
De omvang van het bestand is verwaarloosbaar vergeleken met het gebruik van Excel-formules.

3.4 Werkblad 'VBA_fixed'

Wannneer je niet op zoek bent naar een VBA-benadering die voor allerlei parameters inzetbaar is kun je gebruik maken van een macro die voor slechts 1 parameter-combinatie geschikt is.
In het werkblad 'VBA-fixed' heb ik ter illustratie 3 macro's opgenomen.

Macro kombi5_10 maakt combinaties van 5 elementen uit 10 elementen.
Macro kombi6_10 maakt combinaties van 6 elementen uit 10 elementen.
Macro kombi7_10 maakt combinaties van 7 elementen uit 10 elementen.

Het verschil tussen de macro's is alleen het aantal geneste loops en de grootte van de choose-funktie.
Aan de hand van de drie voorbeelden kun je zelf een macro maken voor de door jou gewenste parameter-combinatie.

In cel B1 is alleen de waarde 10 toegestaan.
In cel B2 zijn de waarden 5, 6 en 7 toegestaan.
In cel B4 schakel je tussen cijfer/label-weergave.

De opzet van deze macro vereist een eigen macro per parameter-combinatie.
Het aantal rijen van een werkblad vormt de beperking van de macro.
Alle berekeningen vinden in het werkgeheugen plaats.
De omvang van de VBA-code is minimaal.
De interaktie met het werkblad is minimaal: 1 x lezen, 1 x schrijven.

De snelheid van de macro is verwaarloosbaar vergeleken met het gebruik van Excel-formules.
De omvang van het bestand is verwaarloosbaar vergeleken met het gebruik van Excel-formules.

3.5 Werkblad 'formulae'

Geef in cel B1 het aantal elementen aan, waaruit combinaties gemaakt moeten worden
Geef in cel B2 aan uit hoeveel elementen een combinatie bestaat.
Een combinatie kan nooit groter zijn dan het aantal elementen in de populatie.
Cel B3 geeft het aantal mogelijke combinaties met de parameters in B1 en B2
In cel B4 schakel je tussen cijfer/label-weergave.

In gebied D1:W3003 staan formules om combinaties te berekenen op basis van de parameters in cel B1 en B2

In gebied AT1:BX31 staat een tabel met een overzicht van het aantal mogelijke combinaties van y elementen uit een set van n elementen.
Daaruit blijkt dat al vrij snel een groot gebied van het werkblad met formules gevuld moet zijn om alle resultaten weer te kunnen geven.
In een groot aantal (grijs gearceerde) gevallen is de omvang van het werkblad zelfs te beperkt.

Ik heb me beperkt tot 3003 rijen. (combinaties van 5 uit 15 of 10 uit 15).
De praktijk leerde dat uitbreiding van het gebied D1:W3003 de omvang van het bestand exponentieel deed toenemen en de rekentijd overeenkomstig vergrootte.
Geen aanrader dus.

In principe is het mogelijk met vrij eenvoudige formules de gewenste combinaties te produceren.
Een voorbeeld daarvan staat in werkblad 'formula_fixed'.
De formules in D2:W3003 zijn zo geformuleerd dat ze via Autofill vanaf kolom W naar kolom D door te trekken zijn en van rij 2 naar de laatste rij van het werkblad.
Daardoor worden de formules wel complexer.
Ze zijn geschikt om combinaties van maximaal 20 elementen te produceren

De cijfer- of labelweergave is niet in de formules ingebouwd.
De formule gebruikt nl. getallen in voorafgaande rijen.
De formule zou onnodig complex worden en de rekentijd daarmee langer.
In plaats daarvan staan in gebied Y1:AR3003 formules om de met D2:W3003 overeenkomende labelwaarden te tonen.

Voor de parameter-combinaties die kleiner of gelijk zijn aan 3003 hoeft er aan de formules niets gewijzigd te worden.

3.6 Werkblad 'formula_fixed'

In gebied D2:H252 staan de formules voor de combinaties van 5 elementen uit 10.
In gebied D1:H1 staan de cijfer 0, 1, 2, 3, 4 'hard' ingevoerd.
De formules zijn niet afhankelijk van de waarden in cel B1 en B2.

De formules in kolom D zijn speciaal voor de 1e positie gemaakt.
Deze kun je wel 'naar beneden' doortrekken, naar niet naar links of rechts.
Datzelfde geldt voor de formules in kolom H.
In de formules in de kolommen E, F en G zijn de maximumwaarden voor iedere positie 'hard' ingevoerd.
Daarom kunnen ook deze formules alleen verticaal doorgetrokken worden.

In de macromodule van werkblad 'VBA' zijn de formules uit gebied D2:H252 vertaald in VBA in Macro M_snb_000.

De dubbelklik-schakelfunktie in cel B4 werkt voor de formules in gebied J1:N252.

Je kunt de formules in dit werkblad gebruiken om voor een eigen vaste parametercombinatie een eigen werkblad te maken.