Permutationer af en matrix i Java

1. Introduktion

I denne artikel vil vi se på, hvordan man opretter permutationer af en matrix.

Først definerer vi, hvad en permutation er. For det andet skal vi se på nogle begrænsninger. Og for det tredje vi ser på tre måder at beregne dem på: rekursivt, iterativt og tilfældigt.

Vi vil fokusere på implementeringen i Java og vil derfor ikke gå ind i mange matematiske detaljer.

2. Hvad er en permutation?

En permutation af et sæt er en omlægning af dets elementer. Et sæt der består af n elementer har n! permutationer. Her n! er det faktuelle, som er produktet af alle positive heltal, der er mindre eller lig med n.

2.1. Eksempel

Matrixen af ​​heltal [3,4,7] har tre elementer og seks permutationer:

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

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

2.2. Begrænsninger

Antallet af permutationer stiger hurtigt med n. Mens det kun tager et par sekunder at generere alle permutationer af ti elementer, vil det tage to uger at generere alle permutationer på 15 elementer:

3. Algoritmer

3.1. Rekursiv algoritme

Den første algoritme, vi ser på, er Heaps algoritme. Det er en rekursiv algoritme, der producerer alle permutationer ved at bytte et element pr. Iteration.

Input arrayet vil blive ændret. Hvis vi ikke ønsker det, skal vi oprette en kopi af arrayet, inden vi kalder metoden:

offentlig statisk ugyldig printAllRecursive (int n, T [] -elementer, char-afgrænser) {if (n == 1) {printArray (elementer, afgrænser); } andet {for (int i = 0; i <n-1; i ++) {printAllRecursive (n - 1, elementer, afgrænser); hvis (n% 2 == 0) {swap (elementer, i, n-1); } ellers {swap (elementer, 0, n-1); }} printAllRecursive (n - 1, elementer, afgrænser); }} 

Metoden bruger to hjælpemetoder:

privat tomrumsudskiftning (T [] input, int a, int b) {T tmp = input [a]; input [a] = input [b]; input [b] = tmp; }
privat ugyldigt printArray (T [] input) {System.out.print ('\ n'); for (int i = 0; i <input.length; i ++) {System.out.print (input [i]); }} 

Her skriver vi resultatet til System.outdog kan vi let gemme resultatet i en matrix eller på en liste i stedet.

3.2. Iterativ algoritme

Heaps algoritme kan også implementeres ved hjælp af iterationer:

int [] indekser = ny int [n]; int [] indekser = ny int [n]; for (int i = 0; i <n; i ++) {indekserer [i] = 0; } printArray (elementer, afgrænser); int i = 0; mens (i <n) {if (indekserer [i] <i) {swap (elementer, i% 2 == 0? 0: indekser [i], i); printArray (elementer, afgrænser); indekser [i] ++; i = 0; } andet {indekserer [i] = 0; i ++; }} 

3.3. Permutationer i leksikografisk rækkefølge

Hvis elementerne er sammenlignelige, kan vi generere permutationer sorteret efter den naturlige orden af elementerne:

offentlig statisk  ugyldig printAllOrdered (T [] -elementer, char-afgrænser) {Arrays.sort (elementer); boolsk hasNext = sand; while (hasNext) {printArray (elementer, afgrænser); 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 = sand; pause; }} for (int i = elements.length - 1; i> k; i--) {if (elementer [i] .compareTo (elementer [k])> 0) {l = i; pause; }} swap (elementer, k, l); Collections.reverse (Arrays.asList (elementer) .subList (k + 1, elements.length)); }} 

Denne algoritme har en baglæns drift i hver iteration, og derfor er den mindre effektiv på arrays end Heaps algoritme.

3.4. Randomiseret algoritme

Hvis n er stor, det kan vi generere en tilfældig permutation ved at blande arrayet:

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

Vi kan gøre dette flere gange for at generere en prøve af permutationer.

Vi kan dog skabe de samme permutationer mere end én gang for store værdier af n, chancerne for at generere den samme permutation to gange er lave.

4. Konklusion

Der er mange måder at generere alle permutationer i et array. I denne artikel så vi den rekursive og iterative Heaps algoritme, og hvordan man genererer en sorteret liste over permutationer.

Det er ikke muligt at generere alle permutationer til store arrays, derfor kan vi generere tilfældige permutationer i stedet.

Implementeringen af ​​alle kodestykker i denne artikel kan findes i vores Github-arkiv.


$config[zx-auto] not found$config[zx-overlay] not found