Informatica I - le permutazioni

Problema delle permutazioni di una stringa

Esaminiamo un problema per il quale è relativamente facile trovare una soluzione ricorsiva, mentre è molto difficile trovarne una iterativa. Un esempio classico è determinare le permutazioni di una stringa, ovvero tutte le stringhe ottenibili utilizzando i caratteri della stringa di partenza in tutte le possibili disposizioni.

Facciamo l'ipotesi che non ci siano caratteri ripetuti. In questo caso, dalla matematica combinatoria sappiamo che il numero di permutazioni di N simboli è N!.

Esempio di permutazioni

Per la stringa "ABC", le permutazioni sono: ABC, ACB, BAC, BCA, CAB, CBA.

Algoritmo ricorsivo per le permutazioni

Utilizziamo un algoritmo ricorsivo per trovare le permutazioni di una stringa di lunghezza N:

• Casobase: se N=1, l'unica permutazione è la stringa stessa.
• Passo ricorsivo: altrimenti:
  • Generiamo tutte le permutazioni che iniziano con il primo carattere,
  • generiamo tutte le permutazioni che iniziano con il secondo carattere,
  • ... e così via. In questo modo otteniamo tutte le possibili permutazioni.

Esempio di codice

public static String[] getPermutations(String word) {
    // Caso base
    if (word.length() == 1)
        return new String[] {word};
    int nperm = 1; // il numero di permutazioni da generare
    for (int i = 2; i <= word.length(); i++)
        nperm *= i; // è il fattoriale di word.length()
    String[] perm = new String[nperm];
    for (int i = 0; i < word.length(); i++) {
        String subword = word.substring(0, i) + word.substring(i + 1);
        // Passo ricorsivo: permutazioni della sottosequenza
        String[] subperm = getPermutations(subword);
        for (int j = 0; j < subperm.length; j++)
            perm[i * subperm.length + j] = word.substring(i, i + 1) + subperm[j];
    }
    return perm;
}