 |
 |
Permutatie en Rangnummer |  |
 |
Inleiding
Permutatie is een ander woord voor volgorde.Een permutatie is een bepaalde volgorde van verschillende dingen.
Aan elke volgorde kunnen we een rangnummer toekennen.
Dit artikel gaat over de koppeling tussen het rangnummer en de permutatie.
Bij een gegeven aantal elementen willen we een permutatie berekenen als de rangorde bekend is.
Of van een gegeven permutatie de rangorde berekenen.
Een (Windows) programma is bijgevoegd, dat deze omrekeningen uitvoert.
Download het programma door op het bliksem icoontje te klikken bovenaan deze pagina.
Er is geen installatieprocedure.
Kopieer het .exe bestandje simpelweg naar een geschikte map.
Faculteit
In de wiskunde komt regelmatig een berekening voor zoals 5*4*3*2*1.Daar is een aparte notatie voor bedacht: 5! spreek uit: vijf faculteit
-
5! = 5*4*3*2*1
-
n! = n*(n-1)*....*3*2*1
Rekenen met faculteiten komt veel voor bij combinatoriek, kansrekening en differentiaalrekening.
Ook heb je het nodig bij het oplossen van logigrammen, sudoku- of andere puzzels.
Hoeveel is 0!
Dit is enigszins maf, want op hoeveel manieren kan je nul voorwerpen op een rijtje zetten?Maar voor gebruik in formules is het handig om 0!=1 te definiëren.
Kijk maar:
4! = 4 * 3!
4! = 4 * 3 * 2!
4! = 4 * 3 * 2 * 1!
4! = 4 * 3 * 2 * 1 * 0!
Vijf verschillende voorwerpen of gebeurtenissen kunnen 5! verschillende volgorden hebben.Als we vijf familieleden achtereenvolgens willen bezoeken, dan kan in 5!= 120 volgorden.
In dit artikel noemen we dingen of gebeurtenissen elementen.
Als element gebruiken we de natuurlijke getallen 1,2,3,4,5........
Laten we alle permutaties van de elementen 1,2,3,4 eens uitschrijven:
rang permutatie 0 1 2 3 4 1 1 2 4 3 2 1 3 2 4 3 1 3 4 2 4 1 4 2 3 5 1 4 3 2 6 2 1 3 4 7 2 1 4 3 8 2 3 1 4 9 2 3 4 1 10 2 4 1 3 11 2 4 3 1 12 3 1 2 4 13 3 1 4 2 14 3 2 1 4 15 3 2 4 1 16 3 4 1 2 17 3 4 2 1 18 4 1 2 3 19 4 1 3 2 20 4 2 1 3 21 4 2 3 1 22 4 3 1 2 23 4 3 2 1We zien 4!=24 permutaties, de rangorde loopt van 0 tot 23.
Deze manier van "tellen" is in zoverre aardig, dat begonnen wordt met 1,2,3,4
en geëindigd met precies de omgekeerde volgorde: 4,3,2,1
In de tabel hierboven merken we op, dat bij rangen 0..5 (de eerste 6) element (1) voorop staat.
Dat is logisch, want de overgebleven elementen 2,3,4, dat zijn er drie, hebben 3!=6 permutaties.
Bij de volgende 6 permutaties staat het tweede element (2) voorop, enzovoorts.
Van rangorde naar permutatie
Het aantal elementen moet bekend zijn.Stel dat zijn er 5, dus 5!=120 en de rangordes lopen van 0 tot en met 119
We schrijven rangordes 0 en 119 uit met daarboven het kolomnummer 1..5
kolom 1 2 3 4 5
0 1 2 3 4 5
. . . . .
119 5 4 3 2 1
Voor rang 0 komen element en kolomnummer overeen.De kolommen 2,3,4,5 (4 elementen) hebben 4!=24 permutaties.
Zodat bij rangordes 0..23 element 1 voorop staat.
Bij rangorde 24 komt element 2 op de eerste plaats.
Voor het eerste element geldt (bij 5 elementen)
kolom = rangorde div 4!
waarbij div een deling is met verwaarlozing van de rest, de cijfers achter de komma vergeten we.Bij rangorde 119 zouden we als eerste element kiezen 119 div 24 = 4, (4+1=5) kolom 5, daar staat element 5.
Let op: +1 omdat de kolommen tellen vanaf 1... en het div resultaat vanaf 0...telt.
Als we uit n elementen bij een bepaald rangnummer r een element moeten kiezen, dan geldt:
kolom := r div (n-1)! + 1
Als een element is gekozen, dan verwijderen we dat uit de rij en schuiven de overgebleven elementen links aan.De rangorde r veranderen we in r = r mod (n-1)!
mod is de rest van een deling. Voorbeelden:
10 mod 3 = 1
11 mod 3 = 2
12 mod 3 = 0
Bij n mod 3 kan het antwoord dus zijn 0,1 of 2.Merk nog op dat voor elk natuurlijk getal N geldt: N = (N div m)*m + (N mod m)
zodat ook: N mod m = N - (N div m)*m
Als voorbeeld berekenen we permutatie nummer 61 van de elementen (1,2,3,4,5)
keuze eerste element (waarna 4 elementen volgen)
4!=24
61 div 24 = 2.....2+1 = 3 ....kies 3e element uit (1,2,3,4,5) dat levert (3 . . . .)
nieuwe rangorde 61 mod 24 = 13
overgebleven elementen (1,2,4,5)
keuze tweede element (waarna 3 elementen volgen)
3!=6
13 div 6 = 2......2+1 = 3.... kies 3e element uit (1,2,4,5) , dat levert (3,4 . . .)
nieuwe rangorde 13 mod 6 = 1
overgebleven elementen (1,2,5)
keuze derde element (waarna 2 elementen volgen)
2!=2
1 div 2 = 0.....0+1=1.......kies 1e element uit( 1,2,5) , dat levert (3,4,1 . .)
nieuwe rangorde 1 mod 2 = 1
overgebleven elementen (2,5)
keuze vierde element(waarna 1 element volgt)
1!=1
1 div 1 = 1 ....1+1=2....kies 2e element uit (2,5) , dat levert (3,4,1,5 .)
nieuwe rangorde 1 mod 1 = 0
overgebleven elementen (2)
keuze vijfde element (waarna 0 elementen volgen)
0!=1
0 div 1 = 0.....0+1=1 kies 1e element uit (2) , dat levert (3,4,1,5,2) het antwoord.
Van permutatie naar rangorde
We gaan weer uit van vijf elementen met permutatie 0 = (1,2,3,4,5).We berekenen de rangorde van de permutatie (5,1,4,2,3).
zet rang= 0
Eerste keuze was 5e element, dus het 4e in de volgorde 0,1,2
De overgebleven 4 elementen hebben 4!=24 permutaties: rang = rang + 4*24= 96
Overgebleven elementen zijn (1,2,3,4), waaruit het eerste (1) werd gekozen.
rang = rang + (1-1)*3! = 96, geen verandering
Overgebleven elementen (2,3,4) , keuze 3e element
rang = rang + (3-1)*2! = 96 + 4 = 100
Overgebleven elementen (2,3) keuze 1e element, geen verhoging rangnummer
Laatse keuze: idem.
Algemeen:Als uit N elementen het e-de element werd gekozen, dan verhoogt het rangnummer met
(e-1)*(N-1)!
Het programma
Het programma is geschreven in de programmeertaal Delphi.Het aantal elementen is instelbaar tot maximaal 12.
De hoogste rangorde is dus 12! - 1 = 479001599, wat nog mooi in een 32 bit integer past.
Vooraf wordt een lijst met de faculteiten van 0..12 gemaakt.
var faclist : array[0..12] of dword;//0! ... 12! .... procedure makepermutationlist; var i : byte; begin faclist[0] := 1; faclist[1] := 1; for i := 2 to 12 do faclist[i] := faclist[i-1]*i; end;variabele maxelement bevat het hoogste element.
perm0 is een lijst die de permutatie met rangnummer 0 bevat.
Rang is de rang van de permutatie.
array element[ ] is de lijst die de permutatie van de elementen bevat.
De procedure die de permutatie berekent is maakpermutatie.
procedure maakpermutatie;
//rang nummer naar permutatie
var rest,pNr : dword;
column,count,i,j : byte;
begin
for i := 1 to maxelement do perm0[i] := i;//maak permutatie 0
pNr := rang;
count := maxelement; //aantal elementen waaruit wordt gekozen
for i := 1 to maxelement do
begin
dec(count);
rest := pNr mod faclist[count];
column := pNr div faclist[count]+1;
element[i] := perm0[column];
for j := column to count do perm0[j] := perm0[j+1];//shift left
pNr := rest;
end;
end;
En hierna bevat het array element[ ] de elementen in de juiste volgorde.Hieronder staat de procedure die van een gegeven permutatie de rang berekent.
perm1[ ] is de permutatie met rang 0, dus (1,2,3,4...)
column is de kolom 1,2,3... die we hieruit kozen.
Na een keuze worden de overgebleven elementen in perm1 links aangeschoven.
elCount is steeds het overgebleven aantal elementen.
procedure maakrang;
//permutatie naar rang conversie
var i,j,elcount : byte;
column : dword;
perm1 : array[1..12] of byte;
begin
elcount := maxelement;
rang := 0;
for i := 1 to elCount do perm1[i] := i;
for i := 1 to elCount do
begin
column := 1;
while element[i] <> perm1[column] do inc(column);
dec(elCount);
rang := rang + (column-1)*faclist[elCount];
for j := column to elCount do perm1[j] := perm1[j+1];//shift left
end;
end;
De procedures zijn maar klein in verhouding tot het gehele project.De meeste regels code zitten in de controle van invoergegevens, oftewel de user interface.
Het gehele Delphi-7 project kan [ HIER ] worden gedownload.
