Een telwerk voor combinaties

download exerciser program
download complete Delphi-7 source code

Voor de theorie van permutaties en combinaties: kijk [hier]

Wat is een combinatie?

Stel we moeten uit een groep van 10 personen er 3 kiezen voor corvee.
Een keuze heet een combinatie.
De volgende vragen rijzen:
    1.hoeveel keuzen zijn er mogelijk?
    2.wat is de volgende keuze gegeven de vorige?
In dit artikel beschrijf ik een Delphi programma dat antwoord geeft op vraag 2.

Even in het kort wat theorie.
10 objecten kan je op 10.9.8.7.6.5.4.3.2.1 = 10! manieren op een rijtje zetten.
10! is een verkorte schrijfwijze, spreek uit : tien faculteit.

De letters van het woord torenflat zijn op 9! manieren op een rijtje te zetten.
Maar neem nu het woord zeemleer.
De letters e zijn het probleem.
Maak dus eerst de e's verschillend, bijvoorbeeld door ze een aparte kleur te geven.
Dan zijn de letters op 8! manieren op een rijtje te zetten.
De e's zijn op 4! manieren op een rijtje te zetten, zodat 8! dus 4! maal te groot is.
Met het woord zeemleer kunnen we dus 8!/4! verschillende "woorden" maken.

Terug naar de corveeploeg.
We kozen 3 personen uit 10.
Dat doen we door ze een bordje op te spelden met Y voor gekozenen en N voor afgewezen personen.
De vraag wordt hiermee: hoeveel "woorden" kan je maken van de letters YYYNNNNNNN ?

Dat is 10! / (3! . 5!)
Immers, 10! is het aantal volgorden als alle letters verschillend zijn.
Maar de Y's zijn op 3! en de N's op 5! manieren op een rijtje te zetten.
Daar moet door worden gedeeld.
Het vorige voorbeeld noemen we : "de combinaties van 3 uit 10".
Ook wel geschreven als C(10,3) = 120.

Algemeen bij K keuzen uit N objecten:
    C(N,K) = N!/(k!.(N-K)!)

Het programma

Hieronder een plaatje van het programma in werking:



De objecten zijn hier de bit posities (1..10).
Een "1" wil zeggen: gekozen, een "0": niet gekozen.
Het plaatje toont de eerste combinatie van 3 uit 10 personen, namelijk de keuze 1,2,3.

De volgende combinatie is logischerwijze: 1,2,4.
Dat gaat zo door tot 1,2,10 en daarna komt 1,3,4......1,3,5.........enzovoorts.
Door op de advance knop te drukken verschijnt steeds de volgende combinatie.

De programma code

Er zijn UP_DOWN tellertjes om het aantal objecten N in te stellen en het aantal keuzes K.
Het maximale aantal objecten is 12.
De variabelen in het programma heten ook N en K.

De combinatie wordt getoond in een paintbox en staat in een word (bits 1..12).
(bit 1 = 1 als object 1 werd gekozen , enz.)
Deze word variable heet SH (van shifter)


Van het word SH worden bits 0 en 13,14,15 niet gebruikt.

RESET

Deze procedure genereert in SH een rijtje van K "1" bits, te beginnen met bit 1.
Merk op dat het word omgekeerd wordt weergegeven: de lagere bits links.
Dat werkt wat prettiger, van links naar rechts.
procedure resetSH;
//set SH to first combination of K out of N
var i : byte;
    mask : word;
begin
 SH := 0;
 mask := 1;
 for i := 1 to K do
  begin
   mask := mask shl 1;
   SH := SH or mask;
  end; 
end;

advanceSH

advanceSH is een functie, die true afgeeft bij een volgende combinatie
en false als de laatste combinatie is bereikt.

Deze functie is wat lastiger dan de vorige.
In unit1 zien we nog deze constante en variabelen:
const maxN = 12;

var N,K : byte;  //K choices out of N objects
    SH  : word;
    timercode : byte;
Om niet herhaald op knopjes te moeten drukken is een timer aangebracht.
Die zorgt voor herhaalde actie zolang een knop blijft ingedrukt.
De timercode bepaalt de actie die de timer moet uitvoeren.
Zie de source code voor details.
function advanceSH : boolean;
//SH shift counter increment
//return true if advanced
//use N,K
var count,pos,i : byte;
    mask : word;
    Done : boolean;
begin
 result := false;
 count := 0;
 pos := N;
 Done := false;
 repeat
  mask := (1 shl pos);
  if SH and mask > 0 then                   //test SH bit
   begin
    SH := SH xor mask;                      //remove 1
    inc(count);                             //count removed 1
    if pos + count <= N then                //test space to shift
     begin
      mask := mask shl 1;                   //next bit
      Done := true;                         
      result := true;
     end
     else
      if count = K then Done := true
       else dec(pos);
   end
   else dec(pos);
 until Done;
 for i := count downto 1 do                 //add removed bits
  begin
   SH := SH xor mask;
   mask := mask shl 1;
  end;
end;
In advanceSH zien we deze variabelen:
    - mask (word): steeds 1 bit set, gebruikt om te vergelijken met bit in SH
    - pos (byte): de positie van het "1" bit in mask
    - count (byte): het aantal verwijderde "1" bits in SH
Er worden twee logische functies gebruikt: and en xor.
Voor de volledigheid nog even wat die doen
    ABA and BA xor B
    0000
    0101
    1001
    1110

Met een and operatie selecteren we bits:



Een xor operatie met "1" draait een bit om ( "0" wordt "1" en "1" wordt "0").
Een xor kan dus een bit setten of resetten.



Hieronder staan twee voorbeelden om het algorithe te laten zien.
1.
Beginstand 1000 (keuze 1 uit 4)
De volgende combinatie is dan 0100.
SH=1000 (binair, volgorde bits omgedraaid om van links naar rechts te werken)
    1. count=0; pos=4; mask=0001(binair)
    2. mask=(1 shl pos)
    3. (mask and SH)=0--> pos-1
    4. mask=0010 (0100,1000)
    5. herhaal 2,3,4 tot pos=1
    6. (mask and SH)>0-->SH xor mask (drop bit);count+1
    7. (pos + count) <= N: Yes--> mask shl 1 (next bit); verlaat repeat loop
    8. (count > 0)? Yes-->set mask in SH, herhaal 8.
    9. return true, volgende combinatie.
Er wordt van rechts naar links naar het eerste "1" bit gezocht.
Dat bit wordt op "0" gezet. Variabele count wordt verhoogd om dit aan te geven.
Als pos+count > N dan is er geen plaats om het "1" bit verder te schuiven.
In dat geval zoeken we naar het volgende "1" bit.
Nadat de repeat loop is verlaten worden de verwijderde "1" bits weer ingevoegd.

2.
Beginstand 000000000111 (laatste combinatie van 3 uit 12).
SH=000000000111 (binair)
    1. count=0;pos=12; (binair)
    2. mask=(1 shl pos)
    3. (mask and SH)>0-->drop bit; count+1
    4. (pos+count)>12 --> pos-1;
    5. herhaal 2,3,4 tot count=3--> verlaat repeat loop
    6. voeg de 3 verwijderde bits weer in
    7. return false, no update
Voor verdere details verwijs ik naar de source code.