Opgave: Schrijf het recursieve algoritme dat alle permutaties van een gegeven woord genereert. Bijvoorbeeld, stel dat het gegeven woord gelijk is aan 'abcd', genereer dan de woorden abcd, abdc, acbd, acdb, adbc, adcb, bacd, badc, bcad, bcda, bdac, bdca, cabd, cadb, cbad, cbda, cdab, cdba, dabc, dacb, dbac, dbca, dcab, dcba. Merk op dat de eerste 6 permutaties gelijk zijn aan de letter 'a', gevolgd door alle permutaties van het woord 'bcd'. De volgende 6 permutaties zijn gelijk aan de letter 'b', gevolgd door alle permutaties van het woord 'acd', ....
http://www.j-walk.com/ss/excel/tips/tip46.htm
http://www.schoolnet.ca/vp/AMOF/e_permI.htm
Tips style="display:none"
Een resursief algoritme heeft steeds een bijzonder en een algemeen geval. Het bijzondere geval is hier eenvoudig. Als het woord maar één letter bevat is er ook maar één permutatie, namelijk het woord zelf. Als het woord meer dan één letter bevat, moet u voor iedere letter alle permutaties genereren van de resterende letters en deze voegen bij de betreffende letter.
- P(woord) = woord als lengte(woord) = 1
- P(woord) = iedere letter van woord + P(woord minus letter) als lengte(woord) > 1
Het recursieve algoritme zal dus beginnen met een test op het bijzondere geval