antirez weblog

A quanto pare nei colloqui alcune aziende chiedono ai candidati di scrivere o quanto meno di esporre il funzionamento di diversi algoritmi. Una domanda che sembra abbastanza in voga e' la seguente:

Dati N elementi scrivere un programma o descrivere un algoritmo che produce tutte le N fattoriale permutazioni

Ad esempio le permutazioni di 'abc' sono le seguenti 6:

abc acb cab bac bca cba

Qualche tempo fa mi serviva per una questione pratica calcolare tutte le permutazioni di una stringa. Dovevo risolvere un problema reale, ma un utilizzo ludico e' sicuramente quello di trovare gli anagrammi di una parola se proprio vi serve uno stimolo ;)

Prima di guardare la letteratura relativa ad un algoritmo su google o in un libro di algoritmi ho l'abitudine di cercare di costruirlo da solo, tanto per tenermi in esercizio, cosi' ho trovato una soluzione semplice che e' facile da ricordare. Sicuramente e' trattata in letteratura da qualche parte ma non so dove e non conosco il nome di questo algoritmo (come potete leggere piu' sotto durante la ricerca di link di approfondimento per questo articolo ho trovato l'algoritmo che sto per illustrare in un sito).

Immaginiamo di voler permutare gli elementi 'abcd'

Pendiamo il primo elemento, 'a'. Le permutazioni di un singolo elemento sono lo stesso elemento, dunque scriviamo

a

Ora prendiamo l'elemento successivo, 'b', e lo inseriamo in tutte le posizioni possibili (ovvero solo prima di 'a' e dopo 'a') per ogni permutazione di 'a', che e' una sola, dunque:

(b)a
a(b)

E queste sono le permutazioni di 'ab'. Ora prendiamo 'c', e per ogni permutazione di 'ab' inseriamo 'c' in ogni possibile posizione:

(c)ba
b(c)a
ba(c)

(c)ab
a(c)b
ab(c)

E cosi' via con la 'd' che inseriremo in ogni posizione possibile di ogni permutazione di 'abc'.

Trasformare questo algoritmo in codice e' banale, tuttavia anche se questo algoritmo e' cosi' semplice non e' molto efficiente. C'e' un algoritmo che sfrutta l'ordine lessicografico degli elementi, ovvero il fatto che per quanto riguarda le stringhe sappiamo dire quale carattere e' maggiore dell'altro (B e' maggiore di A e cosi' via). Tramite questo algoritmo data una qualunque permutazione di una stringa e' possibile calcolare la successiva.

Ovviamente questo puo' essere molto utile perche' permette di creare un oggetto che puo' essere invocato all'interno di un ciclo per restituire la prossima permutazione ogni qual volta la si vuole utilizzare senza generare tutte le permutazioni possibili all'inizio. La descrizione di questo algoritmo e' contenuta in maniera chiara nel secondo link di approfondiemnto. Buon divertimento con permutazioni e anagrammi, per chi volesse cimentarsi :)

p.s. nel secondo link di approfondimenti ho trovato esattamente l'algoritmo da me descritto, che infatti viene considerato come uno dei metodi piu' semplici e naturali di pensare alle permutazioni

Per approfondire

• Permutazioni secondi Wikipedia
• Descrizione dell'algoritmo di permutazioni che sfrutta l'ordine lessicografico (inglese)