Scoprire Anagrammi¶

Una stringa è l’anagramma dell’altra se è un riordino dei caratteri che compaiono nell’altra.

Per esempio, 'heart' e 'earth' sono anagrammi.

Per semplicità assumiamo che le due stringhe in input abbiano la stessa lunghezza e che siano fatte di simboli appartenenti alle 26 lettere, caratteri alfabetici minuscoli. Vogliamo scrivere una funzione booleana che date due stringhe ritorna True se sono una l’anagramma dell’altra.

Soluzione 1: Corrispondenze¶

Possiamo controllare che ogni carattere compaia nella seconda stringa. Siccome vogliamo che se nella prima stringa occorrono due “a” allora anche nella seconda ne occorrano esattamente due, ovvero tutte le lettere devono comparire con la stessa molteplicità in entrambe le stringhe, quando abbiamo trovato la “a” corrispondente nella seconda stringa dobbiamo “spuntarla” perché le “a” che controlleremo successivamente non devono considerarla. Lo facciamo assegnandogli il valore None. Tuttavia, siccome le stringhe in Python sono immutabili, convertiamo prima la stringa in una lista di caratteri.

def anagramSolution1(s1,s2):
    alist = list(s2)

    pos1 = 0
    stillOK = True

    while pos1 < len(s1) and stillOK:
        pos2 = 0
        found = False
        while pos2 < len(alist) and not found:
            if s1[pos1] == alist[pos2]:
                found = True
            else:
                pos2 = pos2 + 1

        if found:
            alist[pos2] = None
        else:
            stillOK = False

        pos1 = pos1 + 1

    return stillOK

print(anagramSolution1('abcd','dcba'))

Checking Off (active5)

Ognuno degli n caratteri in s1 causa una iterazione sugli n caratteri nella lista di s2. Dunque questa soluzione ha complessità temporale \(O(n^{2})\).

Soluzione 2: Ordina e Confronta¶

s1 e s2 sono anagrammi solo se consistono degli stessi caratteri, indipendentemente dall’ordine con cui essi compaiono. Dunque, se ordiniamo le stringhe, affinché esse siano anagrammi, dobbiamo ottenere stringhe uguali. Per ordinare in Python possiamo usare la funzione sort che funziona su liste.

def anagramSolution2(s1,s2):
    alist1 = list(s1)
    alist2 = list(s2)

    alist1.sort()
    alist2.sort()

    pos = 0
    matches = True

    while pos < len(s1) and matches:
        if alist1[pos]==alist2[pos]:
            pos = pos + 1
        else:
            matches = False

    return matches

print(anagramSolution2('abcde','edcba'))

Sort and Compare (active6)

A prima vista potremmo essere tentati di dire che il tempo è \(O(n)\), visto che c’è una solo iterazione su n caratteri dopo l’ordinamento. Tuttavia, come vedremo, le due chiamate Python al metodo sort hanno un costo, che come vedremo è tipicamente \(O(n^{2})\) o \(O(n\log n)\). Dunque, il costo dell’ordinamento domina. Alla fine questo algoritmo avrà lo stesso ordine di costo del processo di ordinamento.

Soluzione 3: Forza Bruta¶

Una tecnica di forza bruta prova ad esplorare tutte le possibili soluzioni. Per esempio, applicandolo al nostro problema, potremmo generare tutte le stringhe che usano i caratteri di s1 e poi controllare se una di queste stringhe è s2. Tuttavia, generando tutte le stringhe possibili di s1, che ha dimensione n, ci sono n possibili primi caratteri, \(n-1\) possibili secondi caratteri, \(n-2\) per il terzo, e così via. Il numero totale di stringhe candidate è \(n*(n-1)*(n-2)*...*3*2*1\), che è \(n!\). Dunque il numero di tali stringhe da generare è \(n!\).

\(n!\) cresce più veloce di \(2^{n}\) quando n diventa grande. Infatti, se s1 è costituito da 20 caratteri, ci potrebbero essere \(20!=2,432,902,008,176,640,000\) possibili stringhe. Se per ogni stringa ci mettessimo 1 secondo, ci vorrebbero comunque 77,146,816,596 anni. Questa dunque non è una buona soluzione.

Soluzione 4: Conta e Confronta¶

Qualsiasi due anagrammi hanno lo stesso numero di a, di b, di c, e così via. Per decidere se due stringhe sono una l’anagramma dell’altra, prima contiamo il numero di occorrenze di ciascuna lettera e poi confrontiamo tali frequenze. Dal momento che sappiamo che ci sono 26 possibili caratteri, possiamo usare una lista di 26 posizioni, una per ciascun carattere. Ogni volta che scorrendo la stringa troviamo un carattere, incrementiamo il contatore corrispondente. Alla fine, se i due vettori delle frequenze sono uguali, allora le due stringhe sono una l’anagramma dell’altra.

def anagramSolution4(s1,s2):
    c1 = [0]*26
    c2 = [0]*26

    for i in range(len(s1)):
        pos = ord(s1[i])-ord('a')
        c1[pos] = c1[pos] + 1

    for i in range(len(s2)):
        pos = ord(s2[i])-ord('a')
        c2[pos] = c2[pos] + 1

    j = 0
    stillOK = True
    while j<26 and stillOK:
        if c1[j]==c2[j]:
            j = j + 1
        else:
            stillOK = False

    return stillOK

print(anagramSolution4('apple','pleap'))

Count and Compare (active7)

La funzione ‘ord’ dato un carattere restituisce un intero che rappresenta il codice Unicode del carattere. Tale codice è consecutivo crescente a partire da ‘a’ per i 26 caratteri.

Per ognuna delle due stringhe, la costruzione del vettore delle frequenze costa la lunghezza dela stringa e corrisponde ai primi due for. L’ultimo for costa al più 26 iterazioni. Dunque otteniamo che il numero di iterazioni totali è \(T(n)=2n+26\), ovvero \(O(n)\), lineare.

Notiamo che, sebbene questo algoritmo sia lineare, esso richiede di memorizzare le frequenze, sacrificando spazio per andare più veloce. In questo caso, il sacrificio non è grande. Le cose sarebbero state diverse se per esempio i caratteri possibili in ciascuna stringa fossero stati migliaia: per esempio, nel caso in cui le stringhe sono lunghe n, ma il numero di simboli che esse accolgono non è noto a priori e possono essere \(2^n\). In tal caso, sarebbe stato utile un dizionario.

Next Section - Sottoarray di Somma Massima