Hier is een oplossing waarmee u de grootte van de permutatie kunt selecteren. Afgezien van het kunnen genereren van alle permutaties van 10 elementen, kan het bijvoorbeeld permutaties van paren van 10 elementen genereren. Het permuteert ook lijsten van willekeurige objecten, niet alleen gehele getallen.
Dit is PHP, maar er is ook JavaScript en Haskell impementation.
function nth_permutation($atoms, $index, $size) {
for ($i = 0; $i < $size; $i++) {
$item = $index % count($atoms);
$index = floor($index/count($atoms));
$result[] = $atoms[$item];
array_splice($atoms, $item, 1);
}
return $result;
}
Gebruik voorbeeld:
for ($i = 0; $i < 6; $i++) {
print_r(nth_permutation(['A', 'B', 'C'], $i, 2));
}
// => AB, BA, CA, AC, BC, CB
Hoe werkt het?
Er zit een heel interessant idee achter. Laten we de lijst A, B, C, D nemen. We kunnen een permutatie construeren door er elementen uit te trekken, zoals uit een pak kaarten. Aanvankelijk kunnen we een van de vier elementen tekenen. Dan een van de drie overgebleven elementen, enzovoort, tot we uiteindelijk niets meer hebben.
Hier is een mogelijke volgorde van keuzes. Vanaf de top nemen we het derde pad, dan het eerste, het tweede en ten slotte het eerste. En dat is onze permutatie # 13.
Denk na over hoe je, gezien deze reeks keuzes, op algoritmisch nummer dertien zou komen. Keer vervolgens uw algoritme om, en zo kunt u de volgorde van een geheel getal reconstrueren.
Laten we proberen een algemeen schema te vinden voor het verpakken van een reeks keuzes in een geheel getal zonder redundantie, en het uitpakken.
Een interessant schema wordt decimaal nummersysteem genoemd. "27" kan worden gezien als het kiezen van pad # 2 van de 10 en vervolgens het kiezen van pad # 7 van de 10.
Maar elk cijfer kan alleen keuzes coderen uit 10 alternatieven. Andere systemen met een vaste radix, zoals binair en hexadecimaal, kunnen ook alleen reeksen keuzes uit een vast aantal alternatieven coderen. We willen een systeem met een variabele radix, een soort tijdseenheden, "14:05:29" is uur 14 van 24, minuut 5 van 60, tweede 29 van 60.
Wat als we generieke nummer-naar-string en string-naar-nummer-functies gebruiken en hen voor de gek houden met het gebruik van gemengde radixen? In plaats van een enkele radix, zoals parseInt ('beef') , 16) en (48879) .toString (16) , nemen ze een radix per cijfer.
function pack(digits, radixes) {
var n = 0;
for (var i = 0; i < digits.length; i++) {
n = n * radixes[i] + digits[i];
}
return n;
}
function unpack(n, radixes) {
var digits = [];
for (var i = radixes.length - 1; i >= 0; i--) {
digits.unshift(n % radixes[i]);
n = Math.floor(n/radixes[i]);
}
return digits;
}
Werkt dat zelfs?
// Decimal system
pack([4, 2], [10, 10]);//=> 42
// Binary system
pack([1, 0, 1, 0, 1, 0], [2, 2, 2, 2, 2, 2]);//=> 42
// Factorial system
pack([1, 3, 0, 0, 0], [5, 4, 3, 2, 1]);//=> 42
En nu achteruit:
unpack(42, [10, 10]);//=> [4, 2]
unpack(42, [5, 4, 3, 2, 1]);//=> [1, 3, 0, 0, 0]
Dit is zo mooi. Laten we nu dit parametrische nummersysteem toepassen op het probleem van permutaties. We overwegen lengte 2 permutaties van A, B, C, D . Wat is het totale aantal van hen? Laten we eens kijken: eerst tekenen we een van de 4 items, dan een van de resterende 3, dat is 4 * 3 = 12 manieren om 2 items te tekenen. Deze 12 manieren kunnen worden ingepakt in gehele getallen [0..11]. Laten we dus doen alsof we ze al hebben ingepakt en proberen uit te pakken:
for (var i = 0; i < 12; i++) {
console.log(unpack(i, [4, 3]));
}
// [0, 0], [0, 1], [0, 2],
// [1, 0], [1, 1], [1, 2],
// [2, 0], [2, 1], [2, 2],
// [3, 0], [3, 1], [3, 2]
Deze getallen vertegenwoordigen keuzes, geen indexen in de oorspronkelijke array. [0, 0] betekent niet dat je A, A gebruikt, dit betekent dat je item # 0 van A, B, C, D (dat is A) en dan item # 0 uit de resterende lijst B, C, D (dat is B). En de resulterende permutatie is A, B .
Nog een voorbeeld: [3, 2] betekent item # 3 van A, B, C, D (dat is D) en vervolgens item # 2 uit de resterende lijst A, B, C (dat is C). En de resulterende permutatie is D, C .
Deze toewijzing wordt Lehmer code genoemd. Laten we al deze Lehmer-codes in kaart brengen voor permutaties:
AB, AC, AD, BA, BC, BD, CA, CB, CD, DA, DB, DC
Dat is precies wat we nodig hebben. Maar als u de functie uitpakken bekijkt, merkt u dat deze cijfers van rechts naar links produceert (om de acties van pack om te keren). De keuze uit 3 wordt uitgepakt voordat de keuze uit 4 wordt gemaakt. Dat is jammer, omdat we willen kiezen uit 4 elementen voordat we uit 3 kiezen. Zonder dit te kunnen doen, moeten we eerst de Lehmer-code berekenen, deze stapelen in een tijdelijke array, en pas het vervolgens toe op de reeks items om de daadwerkelijke permutatie te berekenen.
Maar als we ons niet druk maken om de lexicografische volgorde, kunnen we doen alsof we uit 3 elementen willen kiezen voordat we uit 4 kiezen. Dan komt de keuze uit 4 eerst uit uitpakken . Met andere woorden, we gebruiken uitpakken (n, [3, 4]) in plaats van uitpakken (n, [4, 3]) . Met deze truc kan het volgende cijfer van de Lehmer-code worden berekend en onmiddellijk worden toegepast op de lijst. En dat is precies hoe nth_permutation() werkt.
Een laatste ding dat ik wil vermelden is dat unpack (i, [4, 3]) nauw verwant is met het factoriesysteem. Kijk nogmaals naar die eerste boom, als we permutaties van lengte 2 willen zonder duplicaten, kunnen we elke tweede permutatie-index overslaan. Dat geeft ons 12 permutaties van lengte 4, die op lengte 2 kunnen worden bijgesneden.
for (var i = 0; i < 12; i++) {
var lehmer = unpack(i * 2, [4, 3, 2, 1]);//Factorial number system
console.log(lehmer.slice(0, 2));
}