Egy Java tömbjének permutációi

1. Bemutatkozás

Ebben a cikkben megvizsgáljuk, hogyan hozhatunk létre egy tömb permutációit.

Először meghatározzuk, mi a permutáció. Másodszor megnézünk néhány korlátozást. És harmadszor, három módszert vizsgálunk meg ezek kiszámítására: rekurzív, iteratív és véletlenszerű.

A Java alkalmazásra fogunk összpontosítani, ezért nem fogunk sok matematikai részletességgel foglalkozni.

2. Mi az a permutáció?

A halmaz permutációja elemeinek átrendeződése. Készlet, amely áll n elemek rendelkeznek n! permutációk. Itt n! a faktoriális, amely az összes kisebb vagy egyenlő pozitív egész szám szorzata n.

2.1. Példa

Az [3,4,7] egész számok tömbjének három eleme és hat permutációja van:

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

Permutációk: [3,4,7]; [3,7,4]; [4,7,3]; [4,3,7]; [7,3,4]; [7,4,3]

2.2. Korlátok

A permutáció száma gyorsan növekszik n. Míg tíz elem összes permutációjának generálása csak néhány másodpercet vesz igénybe, 15 hét összes permutációjának előállításához két hétre van szükség:

3. Algoritmusok

3.1. Rekurzív algoritmus

Az első algoritmus, amelyet megnézünk, Heap algoritmusa. Ez egy rekurzív algoritmus, amely minden permutációt úgy állít elő, hogy iterációnként egy elemet cserél.

A bemeneti tömb módosul. Ha ezt nem akarjuk, akkor a módszer meghívása előtt létre kell hoznunk a tömb másolatát:

public static void printAllRecursive (int n, T [] elemek, char határoló) {if (n == 1) {printArray (elemek, elválasztó); } else {for (int i = 0; i <n-1; i ++) {printAllRecursive (n - 1, elemek, elválasztó); if (n% 2 == 0) {csere (elemek, i, n-1); } else {swap (elemek, 0, n-1); }} printAllRecursive (n - 1, elemek, elválasztó); }} 

A módszer két segítő módszert használ:

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

Itt írjuk az eredményt System.outazonban könnyen elmenthetjük az eredményt egy tömbbe vagy egy listába.

3.2. Iteratív algoritmus

Heap algoritmusa iterációk segítségével is megvalósítható:

int [] indexek = új int [n]; int [] indexek = új int [n]; for (int i = 0; i <n; i ++) {indexek [i] = 0; } printArray (elemek, elválasztó); int i = 0; while (i <n) {if (indexek [i] <i) {csere (elemek, i% 2 == 0? 0: indexek [i], i); printArray (elemek, elválasztó); indexek [i] ++; i = 0; } else {indexek [i] = 0; i ++; }} 

3.3. Permutációk lexikográfiai sorrendben

Ha az elemek összehasonlíthatók, akkor generálhatunk a természetes rend szerint rendezett permutációk az elemek közül:

nyilvános statikus  void printAllOrdered (T [] elemek, karakterhatároló) {Tömbök.sort (elemek); logikai hasNext = true; while (hasNext) {printArray (elemek, elválasztó); int k = 0, l = 0; hasNext = hamis; for (int i = elemek.hossz - 1; i> 0; i--) {if (elemek [i] .compareTo (elemek [i - 1])> 0) {k = i - 1; hasNext = true; szünet; }} for (int i = elemek.hossz - 1; i> k; i--) {if (elemek [i] .compareTo (elemek [k])> 0) {l = i; szünet; }} csere (elemek, k, l); Gyűjtemények.reverse (Tömbök.asList (elemek) .subList (k + 1, elemek.hossz)); }} 

Ennek az algoritmusnak van egy fordított minden iterációban működik, ezért tömböknél kevésbé hatékony, mint Heap algoritmusa.

3.4. Véletlenszerű algoritmus

Ha n nagy, tudjuk véletlenszerű permutációt generál a tömb megkeverésével:

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

Ezt többször is megtehetjük, hogy előállítsunk egy mintát a permutációkról.

Előfordulhat, hogy ugyanazokat a permutációkat többször is létrehozzuk, nagy értékekhez n, kicsi az esély arra, hogy kétszer ugyanazt a permutációt generáljuk.

4. Következtetés

Sokféle módon lehet létrehozni egy tömb összes permutációját. Ebben a cikkben láttuk a rekurzív és iteratív Heap algoritmusát, valamint a permutációk rendezett listájának létrehozásának módját.

Nem megvalósítható az összes permutáció generálása nagy tömbökhöz, ezért helyette véletlenszerű permutációkat is létrehozhatunk.

A cikkben szereplő összes kódrészlet megvalósítása megtalálható a Github-adattárunkban.