Permutazioni di un array in Java

1. Introduzione

In questo articolo vedremo come creare permutazioni di un array.

Per prima cosa, definiremo cos'è una permutazione. In secondo luogo, esamineremo alcuni vincoli. E terzo, esamineremo tre modi per calcolarli: in modo ricorsivo, iterativo e casuale.

Ci concentreremo sull'implementazione in Java e quindi non entreremo in molti dettagli matematici.

2. Che cos'è una permutazione?

Una permutazione di un insieme è un riarrangiamento dei suoi elementi. Un insieme che consiste di n elementi ha n! permutazioni. Qui n! è il fattoriale, che è il prodotto di tutti i numeri interi positivi minori o uguali a n .

2.1. Esempio

L'array di interi [3,4,7] ha tre elementi e sei permutazioni:

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

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

2.2. Vincoli

Il numero di permutazioni aumenta velocemente con n . Sebbene siano necessari solo pochi secondi per generare tutte le permutazioni di dieci elementi, ci vorranno due settimane per generare tutte le permutazioni di 15 elementi:

3. Algoritmi

3.1. Algoritmo ricorsivo

Il primo algoritmo che esaminiamo è l'algoritmo di Heap. È un algoritmo ricorsivo che produce tutte le permutazioni scambiando un elemento per iterazione.

La matrice di input verrà modificata. Se non lo vogliamo, dobbiamo creare una copia dell'array prima di chiamare il metodo:

public static  void printAllRecursive( int n, T[] elements, char delimiter) { if(n == 1) { printArray(elements, delimiter); } 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, elements, delimiter); } } 

Il metodo utilizza due metodi di supporto:

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

Qui, scriviamo il risultato in System.out , tuttavia, possiamo facilmente memorizzare il risultato in un array o in un elenco.

3.2. Algoritmo iterativo

L'algoritmo di Heap può essere implementato anche utilizzando iterazioni:

int[] indexes = new int[n]; int[] indexes = new int[n]; for (int i = 0; i < n; i++) { indexes[i] = 0; } printArray(elements, delimiter); int i = 0; while (i < n) { if (indexes[i] < i) { swap(elements, i % 2 == 0 ? 0: indexes[i], i); printArray(elements, delimiter); indexes[i]++; i = 0; } else { indexes[i] = 0; i++; } } 

3.3. Permutazioni in ordine lessicografico

Se gli elementi sono confrontabili, possiamo generare permutazioni ordinate in base all'ordine naturale degli elementi:

public static 
    
      void printAllOrdered( T[] elements, char delimiter) { Arrays.sort(elements); boolean hasNext = true; while(hasNext) { printArray(elements, delimiter); 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; break; } } for (int i = elements.length - 1; i > k; i--) { if (elements[i].compareTo(elements[k]) > 0) { l = i; break; } } swap(elements, k, l); Collections.reverse(Arrays.asList(elements).subList(k + 1, elements.length)); } } 
    

Questo algoritmo ha un'operazione inversa in ogni iterazione e quindi è meno efficiente sugli array rispetto all'algoritmo di Heap.

3.4. Algoritmo randomizzato

Se n è grande, possiamo generare una permutazione casuale mescolando l'array:

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

Possiamo farlo più volte per generare un campione di permutazioni.

Potremmo creare le stesse permutazioni più di una volta, tuttavia, per valori elevati di n , le possibilità di generare due volte la stessa permutazione sono basse.

4. Conclusione

Esistono molti modi per generare tutte le permutazioni di un array. In questo articolo, abbiamo visto l'algoritmo di Heap ricorsivo e iterativo e come generare un elenco ordinato di permutazioni.

Non è possibile generare tutte le permutazioni per array di grandi dimensioni, quindi possiamo generare permutazioni casuali.

L'implementazione di tutti i frammenti di codice in questo articolo può essere trovata nel nostro repository Github.