Permutasjoner av en matrise i Java

1. Introduksjon

I denne artikkelen vil vi se på hvordan du lager permutasjoner av en matrise.

Først vil vi definere hva en permutasjon er. For det andre skal vi se på noen begrensninger. Og for det tredje, vi vil se på tre måter å beregne dem på: rekursivt, iterativt og tilfeldig.

Vi vil fokusere på implementeringen i Java og vil derfor ikke gå i mye matematisk detalj.

2. Hva er en permutasjon?

En permutasjon av et sett er en omorganisering av elementene. Et sett som består av n elementer har n! kombinasjonsmuligheter. Her n! er faktoriet, som er et produkt av alle positive heltall som er mindre eller lik n.

2.1. Eksempel

Utvalget av heltall [3,4,7] har tre elementer og seks permutasjoner:

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

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

2.2. Begrensninger

Antallet permutasjoner øker raskt med n. Selv om det bare tar noen få sekunder å generere alle permutasjoner av ti elementer, vil det ta to uker å generere alle permutasjoner på 15 elementer:

3. Algoritmer

3.1. Rekursiv algoritme

Den første algoritmen vi ser på er Heaps algoritme. Det er en rekursiv algoritme som produserer alle permutasjoner ved å bytte ett element per iterasjon.

Inngangsoppsettet blir endret. Hvis vi ikke vil ha det, må vi lage en kopi av matrisen før vi kaller metoden:

public static void printAllRecursive (int n, T [] elements, char delimiter) {if (n == 1) {printArray (elements, delimiter); } annet {for (int i = 0; i <n-1; i ++) {printAllRecursive (n - 1, elementer, skilletegn); hvis (n% 2 == 0) {bytte (elementer, i, n-1); } annet {bytte (elementer, 0, n-1); }} printAllRecursive (n - 1, elementer, skilletegn); }} 

Metoden bruker to hjelpermetoder:

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

Her skriver vi resultatet til System.outimidlertid kan vi enkelt lagre resultatet i en matrise eller i en liste i stedet.

3.2. Iterativ algoritme

Heaps algoritme kan også implementeres ved hjelp av iterasjoner:

int [] indekser = ny int [n]; int [] indekser = ny int [n]; for (int i = 0; i <n; i ++) {indekserer [i] = 0; } printArray (elementer, skilletegn); int i = 0; mens (i <n) {if (indekserer [i] <i) {bytte (elementer, i% 2 == 0? 0: indekser [i], i); printArray (elementer, skilletegn); indekser [i] ++; i = 0; } annet {indekserer [i] = 0; i ++; }} 

3.3. Permutasjoner i leksikografisk rekkefølge

Hvis elementene er sammenlignbare, kan vi generere permutasjoner sortert etter den naturlige ordenen av elementene:

offentlig statisk  ugyldig printAllOrdered (T [] -elementer, skille avgrensning) {Arrays.sort (elementer); boolsk hasNext = true; while (hasNext) {printArray (elementer, skilletegn); 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; gå i stykker; }} for (int i = elements.length - 1; i> k; i--) {if (elements [i] .compareTo (elements [k])> 0) {l = i; gå i stykker; }} bytte (elementer, k, l); Collections.reverse (Arrays.asList (elements) .subList (k + 1, elements.length)); }} 

Denne algoritmen har en omvendt drift i hver iterasjon, og derfor er den mindre effektiv på matriser enn Heaps algoritme.

3.4. Tilfeldig algoritme

Hvis n er stor, det kan vi generere en tilfeldig permutasjon ved å blande blandingen:

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

Vi kan gjøre dette flere ganger for å generere et utvalg av permutasjoner.

Vi kan imidlertid opprette de samme permutasjonene mer enn en gang for store verdier av n, sjansene for å generere den samme permutasjonen to ganger er lave.

4. Konklusjon

Det er mange måter å generere alle permutasjoner i en matrise. I denne artikkelen så vi den rekursive og iterative Heaps algoritme og hvordan man genererer en sortert liste over permutasjoner.

Det er ikke mulig å generere alle permutasjoner for store matriser, derfor kan vi generere tilfeldige permutasjoner i stedet.

Implementeringen av alle kodebiter i denne artikkelen finner du i Github-arkivet vårt.