Helemaal suf...

[Sjoerd Job]

Omdat volgorde niet uit maakt, kunnen we elke combinatie sorteren, zodat het de volgorde abcdefghi... volgt...

laten we dan beginnen... we zoeken combinaties van lengte r, met n symbolen.

ik beschrijf het eerst met n=7, r=5 (abcdefg)

Elke combinatie begint met een symbool. Dit symbool kan zijn
a
b
c

merk op, als we beginnen met d, kunnen we als combinatie van 5 lang defgh maken, maar dat past niet... dus mogen we niet met d of later beginnen.

nu, als tweede keuze hebben we voor de tweede positie mag geen e of hoger optreden.
ab
ac
ad
bc
bd
cd

Als derde keuze kunnen we krijgen
abc
abd
abe
acd
ace
ade
bcd
bce
cde
merk op dat we nu niet f of hoger mogen.
alweer verder

abcd
abce
abcf
abde
abdf
abef
acde
acdf
acef
adef
bcde
bcdf
bcef
cdef

als vijfde komen we dan op
abcde
abcdf
abcdg
abcef
abceg
abcfg
abdef
abdeg
abdfg
abefg
acdef
acdeg
acdfg
acefg
adefg
bcdef
bcdeg
bcdfg
bcefg
cdefg

zie je hoe het lijstje is gegenereerd?

Laten we dit omzetten in een algorithme, maar eerst een aantal definities:
Definitie 1: Symbool Een symbool is datgene waar we combinaties van willen maken. In deze uitwerking correspondeert de verzameling van symbolen met de verzameling

Definitie 2: Een lijst Een lijst is een object dat 0 of meer objecten bevat. De lege lijst noteren we met (), een lijst met 1 object als (object), en met meer objecten als (object1, ..., object n). Een object mag eventueel ook een lijst zijn, maar kan ook een symbool zijn. Merk op dat de volgorde van de lijst er toe doet. (zo kunnen we praten over het nde object in een lijst), en we noteren het nde element van lijst a met .

Definite 3: Concanatie Gegeven twee lijsten met lengte en met lengte definieren we de concatenatie als de lijst met lengte zodat als , het de element van correspondeert met het de element van , en voor alle , we een correspondentie hebben met ... oftewel, schrijf ze achter elkaar, en laat de tussenliggende haakjes weg, om ze met een komma te vervangen.

Definitie 4: Interne toevoeging De interne toevoeging van lijst op lijst van lijsten noteren we als voldoet aan , oftewel concateneer op elk element van .

Definitie 5: Droppen van eerste element De functie voldoet aan

Definitie 6: Lengte van een lijst De functie voldoet aan =0, en


Geldende deze definities, dan wordt het lijstje van alle combinaties gegeven door



Probeer de functie maar eens uit te voeren aan de hand van het 7,5 voorbeeld... als het goed is doet hij het.