Permutácie poľa v Jave

1. Úvod

V tomto článku sa pozrieme na to, ako vytvoriť permutácie poľa.

Najskôr definujeme, čo je to permutácia. Po druhé, pozrieme sa na niektoré obmedzenia. A po tretie, Pozrime sa na tri spôsoby, ako ich vypočítať: rekurzívne, iteratívne a náhodne.

Zameriame sa na implementáciu v Jave, a preto sa nebudeme venovať veľmi matematickým detailom.

2. Čo je to permutácia?

Permutácia sady je preskupenie jej prvkov. Sada, ktorá sa skladá z n prvkov má n! permutácie. Tu n! je faktoriál, ktorý je produktom všetkých kladných celých čísel menších alebo rovných n.

2.1. Príklad

Pole celých čísel [3,4,7] má tri prvky a šesť permutácií:

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

Permutácie: [3,4,7]; [3,7,4]; [4,7,3]; [4,3,7]; [7,3,4]; [7,4,3]

2.2. Obmedzenia

Počet permutácií sa rýchlo zvyšuje n. Aj keď generovanie všetkých permutácií desiatich prvkov trvá iba pár sekúnd, vygenerovanie všetkých permutácií 15 prvkov bude trvať dva týždne:

3. Algoritmy

3.1. Rekurzívny algoritmus

Prvý algoritmus, na ktorý sa pozrieme, je Heapov algoritmus. Je to rekurzívny algoritmus, ktorý vytvára všetky permutácie zamenením jedného prvku za iteráciu.

Vstupné pole bude upravené. Ak to nechceme, pred vytvorením metódy musíme vytvoriť kópiu poľa:

public static void printAllRecursive (int n, T [] prvky, oddeľovač znakov) {if (n == 1) {printArray (prvky, oddeľovač); } else {for (int i = 0; i <n-1; i ++) {printAllRecursive (n - 1, elements, delimiter); if (n% 2 == 0) {swap (elements, i, n-1); } else {swap (elements, 0, n-1); }} printAllRecursive (n - 1, prvky, oddeľovač); }} 

Metóda používa dve pomocné metódy:

swap private void (T [] vstup, int a, int b) {T tmp = vstup [a]; vstup [a] = vstup [b]; vstup [b] = tmp; }
private void printArray (vstup T []) {System.out.print ('\ n'); pre (int i = 0; i <input.length; i ++) {System.out.print (vstup [i]); }} 

Tu výsledok zapíšeme do System.out, Výsledok však môžeme jednoducho uložiť do poľa alebo do zoznamu.

3.2. Iteratívny algoritmus

Heapov algoritmus je možné implementovať aj pomocou iterácií:

int [] indexy = nový int [n]; int [] indexy = nový int [n]; for (int i = 0; i <n; i ++) {indexes [i] = 0; } printArray (prvky, oddeľovač); int i = 0; while (i <n) {if (indexes [i] <i) {swap (elements, i% 2 == 0? 0: indexes [i], i); printArray (prvky, oddeľovač); indexy [i] ++; i = 0; } else {indexy [i] = 0; i ++; }} 

3.3. Permutácie v lexikografickom poradí

Ak sú prvky porovnateľné, môžeme ich vygenerovať permutácie zoradené podľa prirodzeného poriadku prvkov:

verejná statická  void printAllOrdered (prvky T [], oddeľovač znakov) {Arrays.sort (prvky); boolean hasNext = true; while (hasNext) {printArray (elements, delimiter); int k = 0, l = 0; hasNext = false; pre (int i = elements.length - 1; i> 0; i--) {if (elements [i] .compareTo (elements [i - 1])> 0) {k = i - 1; hasNext = true; prestávka; }} pre (int i = elements.length - 1; i> k; i--) {if (elements [i] .compareTo (elements [k])> 0) {l = i; prestávka; }} zamenit (prvky, k, l); Collections.reverse (Arrays.asList (elements) .subList (k + 1, elements.length)); }} 

Tento algoritmus má a obrátiť operácia v každej iterácii, a preto je na poliach menej efektívna ako Heapov algoritmus.

3.4. Randomizovaný algoritmus

Ak n je veľký, môžeme generovať náhodnú permutáciu premiešaním poľa:

Zbierky.shuffle (Arrays.asList (prvky));

Môžeme to urobiť niekoľkokrát, aby sme vygenerovali vzorku permutácií.

Mohli by sme však vytvoriť rovnaké permutácie viackrát, pre veľké hodnoty n, šance na generovanie rovnakej permutácie dvakrát sú nízke.

4. Záver

Existuje mnoho spôsobov, ako generovať všetky permutácie poľa. V tomto článku sme videli rekurzívny a iteratívny Heapov algoritmus a spôsob generovania triedeného zoznamu permutácií.

Nie je možné generovať všetky permutácie pre veľké polia, preto môžeme namiesto nich generovať náhodné permutácie.

Implementáciu všetkých útržkov kódu v tomto článku nájdete v našom úložisku Github.


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