Una permutazione di lunghezza n è una raccolta ordinata senza ripetizioni dei numeri 1, 2, ..., n. Ad esempio, [3, 1, 2] e [5, 4, 3, 2, 1] sono permutazioni, ma [1, 2, 1, 3] e [1, 2, 4] non lo sono.
Se l'attività si riduce al fatto che è necessario iterare su tutte le permutazioni di lunghezza n, è possibile utilizzare un comodo meccanismo in C ++, che si chiama "next_permutation".
Puoi saperne di più nella documentazione, ma il punto è che questa funzione cambia l'array passato alla successiva permutazione in ordine lessicografico (che è generalmente chiaro e il suo nome).
Per utilizzare next_permutation, devi includere la libreria dell'algoritmo (ovvero scrivi #include <algorithm> all'inizio del programma)
Esempi:
vettore arr;
arr = {1, 2, 3}; // l'array è [1, 2, 3]
next_permutation(arr.begin(), arr.end()); // passa l'intero array alla funzione
// l'array ora è [1, 3, 2]
arr = { 2, 3, 1 }; // l'array è [2, 3, 1]
next_permutation(arr.begin(), arr.end()); // passa l'intero array alla funzione
// l'array ora è [3, 1, 2]
next_permutation(arr.begin() + 1, arr.begin() + 3); // è possibile applicare una funzione a una parte di un array, ma in pratica ciò è raramente necessario
// l'array ora è [3, 2, 1]
In questo caso, la funzione ha un valore di ritorno booleano che è vero se è stata generata la permutazione successiva e falso se non ce n'è stata una successiva (il caso in cui la permutazione massima in ordine lessicografico viene passata alla funzione).
Ciò rende possibile utilizzare la funzione in un ciclo, che ci consentirà di iterare su tutte le permutazioni contemporaneamente. A causa dell'indicizzazione 0, in pratica è spesso più conveniente lavorare con una permutazione di numeri da 0 a n - 1, sebbene una permutazione contenga formalmente numeri da 1 a n. Ma fortunatamente, questo non porta a ulteriori sovrapposizioni nel codice, perché la funzione next_permutation è adattata alle permutazioni con indice 0 (e persino agli elementi duplicati in un array, ma puoi scoprirne di più da solo).
In generale, il codice per l'iterazione di tutte le permutazioni è simile al seguente:
int; // dimensione della permutazione
vettoreperm(n); // perm è l'abbreviazione di "permutazione", cioè "permutazione"
for (int i = 0; i < n; i++)
perm[i] = i; // inizializza la permutazione iniziale 0, 1, ..., n - 1
Fare {
// all'interno del ciclo elaboriamo la permutazione corrente
} while (next_permutation(perm.begin(), perm.end())); // se non c'è una permutazione successiva, termina il ciclo
Questo codice viene eseguito in O(n! * f(n)), dove f(n) è il tempo necessario per elaborare una particolare permutazione.