11.3.10 Trovare anagrammi da una lista di parole

Un’interessante sfida per il programmatore è quella di cercare anagrammi in una lista di parole (come /usr/share/dict/italian presente in molti sistemi GNU/Linux). Una parola è un anagramma di un’altra se entrambe le parole contengono le stesse lettere (p.es., “branzino” e “bronzina”).

La Colonna 2, Problema C, della seconda edizione del libro di Jon Bentley Programming Pearls, presenta un algoritmo elegante. L’idea è di assegnare a parole che sono anagrammi l’una dell’altra una firma comune, e poi di ordinare tutte le parole in base alla loro firma e di stamparle. Il Dr. Bentley fa notare che prendere tutte le lettere di ogni parola ed elencarle in ordine alfabetico produce queste firme comuni.

Il programma seguente usa vettori di vettori per riunire parole con la stessa firma, e l’ordinamento di vettori per stampare le parole trovate in ordine alfabetico:

# anagram.awk --- Un'implementazione dell'algoritmo per trovare anagrammi
#                 dalla seconda edizione
#                 del libro di Jon Bentley "Programming Pearls".
#                 Addison Wesley, 2000, ISBN 0-201-65788-0.
#                 Colonna 2, Problema C, sezione 2.8, pp 18-20.

/'s$/   { next }        # Salta i genitivi sassoni

Il programma inizia con un’intestazione, e poi una regola per saltare i genitivi sassoni eventualmente contenuti nel file che contiene la lista di parole. La regola successiva costruisce la struttura dei dati. Il primo indice del vettore è rappresentato dalla firma; il secondo è la parola stessa:

{
    chiave = da_parola_a_chiave($1)  # costruisce la firma
    data[chiave][$1] = $1  # Immagazzina parola con questa firma
}

La funzione da_parola_a_chiave() crea la firma. Divide la parola in lettere singole, mette in ordine alfabetico le lettere, e poi le rimette ancora insieme:

# da_parola_a_chiave --- divide parole in lettere, ordina e riunisce

function da_parola_a_chiave(parola,     a, i, n, risultato)
{
    n = split(parola, a, "")
    asort(a)

    for (i = 1; i <= n; i++)
        risultato = risultato a[i]

    return risultato
}

Infine, la regola END percorre tutto il vettore e stampa le liste degli anagrammi. L’output è poi passato al comando di sistema sort perché altrimenti gli anagrammi sarebbero elencati in ordine arbitrario:

END {
    sort = "sort"
    for (chiave in data) {
        # ordina parole con la stessa chiave
        n_parole = asorti(data[chiave], parole)
        if (n_parole == 1)
            continue

        # e stampa. Problema minore: uno spazio extra a fine di ogni riga
        for (j = 1; j <= n_parole; j++)
            printf("%s ", parole[j]) | sort
        print "" | sort
    }
    close(sort)
}

Ecco una piccola parte dell’output quando il programma è eseguito:

$ gawk -f anagram.awk /usr/share/dict/italian | grep '^b'
…
baraste bastare serbata
barasti basarti
baratro tabarro
barattoli ribaltato tribolata
barbieri birberia
barche brache
barcollerei corbelleria
bare erba
bareremmo brameremo
barili librai
…