streamalism.org

1. Uvod

U ovom ćemo članku pogledati kako stvoriti permutacije niza.

Prvo ćemo definirati što je permutacija. Drugo, pogledat ćemo neka ograničenja. I treće, pogledat ćemo tri načina za njihovo izračunavanje: rekurzivno, iterativno i nasumično.

Usredotočit ćemo se na implementaciju u Javi i stoga nećemo ulaziti u puno matematičkih detalja.

2. Što je permutacija?

Permutacija skupa je preslagivanje njegovih elemenata. Skup koji se sastoji od n elementi ima n! permutacije. Ovdje n! je faktorijel, koji je umnožak svih pozitivnih cijelih brojeva manjih ili jednakih n.

2.1. Primjer

Niz cijelih brojeva [3,4,7] ima tri elementa i šest permutacija:

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

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

2.2. Ograničenja

Broj permutacija se brzo povećava s n. Iako je potrebno samo nekoliko sekundi za generiranje svih permutacija od deset elemenata, trebat će dva tjedna da bi se generirale sve permutacije od 15 elemenata:

3. Algoritmi

3.1. Rekurzivni algoritam

Prvi algoritam koji gledamo je Heapov algoritam. To je rekurzivni algoritam koji proizvodi sve permutacije zamjenom jednog elementa po iteraciji.

Ulazni niz će se izmijeniti. Ako to ne želimo, moramo stvoriti kopiju niza prije pozivanja metode:

javna statička praznina printAllRecursive (int n, T [] elementi, razgraničenje znakova) {if (n == 1) {printArray (elementi, razgraničenje); } else {for (int i = 0; i <n-1; i ++) {printAllRecursive (n - 1, elementi, graničnik); if (n% 2 == 0) {swap (elementi, i, n-1); } else {swap (elementi, 0, n-1); }} printAllRecursive (n - 1, elementi, graničnik); }} 

Metoda koristi dvije pomoćne metode:

zamjena privatne praznine (T [] ulaz, int a, int b) {T tmp = ulaz [a]; ulaz [a] = ulaz [b]; ulaz [b] = tmp; }

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

Ovdje zapisujemo rezultat System.out, međutim, rezultat možemo jednostavno pohraniti u niz ili na popis.

3.2. Iterativni algoritam

Heap-ov algoritam također se može implementirati pomoću iteracija:

indeksi int [] = novi int [n]; indeksi int [] = novi int [n]; za (int i = 0; i <n; i ++) {indeksi [i] = 0; } printArray (elementi, graničnik); int i = 0; while (i <n) {if (indeks [i] <i) {swap (elementi, i% 2 == 0? 0: indeksi [i], i); printArray (elementi, graničnik); indeksi [i] ++; i = 0; } else {indeksi [i] = 0; i ++; }} 

3.3. Permutacije u leksikografskom poretku

Ako su elementi usporedivi, možemo generirati permutacije sortirane po prirodnom redu od elemenata:

javna statika  void printAllOrdered (T [] elementi, razgraničenje znakova) {Arrays.sort (elements); boolean hasNext = true; while (hasNext) {printArray (elementi, graničnik); 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; pauza; }} for (int i = elements.length - 1; i> k; i--) {if (elements [i] .compareTo (elements [k])> 0) {l = i; pauza; }} swap (elementi, k, l); Collections.reverse (Arrays.asList (elements) .subList (k + 1, elements.length)); }} 

Ovaj algoritam ima obrnuti operacija u svakoj iteraciji i zato je manje učinkovit na nizovima od Heap-ovog algoritma.

3.4. Randomizirani algoritam

Ako n je velika, možemo generirati slučajnu permutaciju miješanjem niza:

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

To možemo učiniti nekoliko puta da generiramo uzorak permutacija.

Međutim, mogli bismo stvoriti iste permutacije više puta, međutim, za velike vrijednosti n, šanse za generiranje iste permutacije dva puta su malene.

4. Zaključak

Postoji mnogo načina za generiranje svih permutacija niza. U ovom smo članku vidjeli rekurzivni i iterativni algoritam Heap i kako generirati sortirani popis permutacija.

Nije izvedivo generirati sve permutacije za velike nizove, stoga umjesto toga možemo generirati slučajne permutacije.

Implementacija svih isječaka koda u ovom članku može se naći u našem spremištu Github.