streamalism.org

1. Inleiding

In dit artikel zullen we bekijken hoe u permutaties van een array kunt maken.

Eerst zullen we definiëren wat een permutatie is. Ten tweede zullen we enkele beperkingen bekijken. En ten derde, we zullen drie manieren bekijken om ze te berekenen: recursief, iteratief en willekeurig.

We zullen ons concentreren op de implementatie in Java en daarom niet op veel wiskundige details ingaan.

2. Wat is een permutatie?

Een permutatie van een set is een herschikking van de elementen. Een set die bestaat uit n elementen heeft n! permutaties. Hier n! is de faculteit, die het product is van alle positieve gehele getallen kleiner of gelijk aan n.

2.1. Voorbeeld

De reeks gehele getallen [3,4,7] heeft drie elementen en zes permutaties:

n! = 3! = 1 x 2 x 3 = 6

Permutaties: [3,4,7]; [3,7,4]; [4,7,3]; [4,3,7]; [7,3,4]; [7,4,3]

2.2. Beperkingen

Het aantal permutaties neemt snel toe met n. Hoewel het slechts een paar seconden duurt om alle permutaties van tien elementen te genereren, duurt het twee weken om alle permutaties van 15 elementen te genereren:

3. Algoritmen

3.1. Recursief algoritme

Het eerste algoritme dat we bekijken, is het algoritme van Heap. Het is een recursief algoritme dat alle permutaties produceert door één element per iteratie om te wisselen.

De invoerarray wordt gewijzigd. Als we dat niet willen, moeten we een kopie van de array maken voordat we de methode aanroepen:

openbare statische leegte printAllRecursive (int n, T [] elementen, scheidingsteken tekens) {if (n == 1) {printArray (elementen, scheidingsteken); } else {for (int i = 0; i <n-1; i ++) {printAllRecursive (n - 1, elementen, scheidingsteken); if (n% 2 == 0) {swap (elementen, i, n-1); } else {swap (elementen, 0, n-1); }} printAllRecursive (n - 1, elementen, scheidingsteken); }} 

De methode gebruikt twee hulpmethoden:

private void swap (T [] input, int a, int b) {T tmp = input [a]; input [a] = input [b]; invoer [b] = tmp; }

private void printArray (T [] invoer) {System.out.print ('\ n'); for (int i = 0; i <input.length; i ++) {System.out.print (input [i]); }} 

Hier schrijven we het resultaat naar System.outwe kunnen het resultaat echter gemakkelijk opslaan in een array of in een lijst.

3.2. Iteratief algoritme

Het algoritme van Heap kan ook worden geïmplementeerd met iteraties:

int [] indexes = nieuwe int [n]; int [] indexes = nieuwe int [n]; voor (int i = 0; i <n; i ++) {indexen [i] = 0; } printArray (elementen, scheidingsteken); int i = 0; while (i <n) {if (indexen [i] <i) {swap (elementen, i% 2 == 0? 0: indexen [i], i); printArray (elementen, scheidingsteken); indexeert [i] ++; i = 0; } anders {indexen [i] = 0; i ++; }} 

3.3. Permutaties in lexicografische volgorde

Als de elementen vergelijkbaar zijn, kunnen we genereren permutaties gesorteerd op de natuurlijke volgorde van de elementen:

openbare statische  void printAllOrdered (T [] elementen, scheidingsteken tekens) {Arrays.sort (elementen); boolean hasNext = true; while (hasNext) {printArray (elementen, scheidingsteken); int k = 0, l = 0; hasNext = false; for (int i = elements.length - 1; i> 0; i--) {if (elements [i] .compareTo (elements [i - 1])> 0) {k = i - 1; hasNext = true; breken; }} for (int i = elements.length - 1; i> k; i--) {if (elements [i] .compareTo (elements [k])> 0) {l = i; breken; }} swap (elementen, k, l); Collections.reverse (Arrays.asList (elementen) .subList (k + 1, elements.length)); }} 

Dit algoritme heeft een omgekeerde bewerking in elke iteratie en daarom is het minder efficiënt op arrays dan het algoritme van Heap.

3.4. Gerandomiseerd algoritme

Als n is groot, we kunnen genereer een willekeurige permutatie door de array te schudden:

Collections.shuffle (Arrays.asList (elementen));

We kunnen dit meerdere keren doen om een ​​voorbeeld van permutaties te genereren.

We kunnen dezelfde permutaties echter meer dan eens maken voor grote waarden van n, is de kans om twee keer dezelfde permutatie te genereren laag.

4. Conclusie

Er zijn veel manieren om alle permutaties van een array te genereren. In dit artikel hebben we het recursieve en iteratieve Heap-algoritme gezien en hoe een gesorteerde lijst met permutaties kan worden gegenereerd.

Het is niet haalbaar om alle permutaties voor grote arrays te genereren, daarom kunnen we in plaats daarvan willekeurige permutaties genereren.

De implementatie van alle codefragmenten in dit artikel is te vinden in onze Github-repository.