Introduzione a Divide et Impera e conteggio delle inversioni¶
A cura di Carla Galluccio
1 Introduzione¶
Con Divide et Impera ci si riferisce ad una classe di tecniche algoritmiche che consistono nella risoluzione di un problema mediante la sua suddivisione in sotto-problemi (dello stesso tipo del problema di partenza), la risoluzione singola di ognuno di essi ricorsivamente e, infine, la combinazione delle soluzioni di tutti i sotto-problemi in una soluzione generale per il problema di partenza. Solitamente, questa tecnica viene utilizzata dividendo il problema iniziale in due sotto-problemi, possibilmente di dimensioni pari alla metà della dimensione del problema di partenza, ovvero \(n/2\).
Una caratteristica di queste tecniche algoritmiche è che, nei contesti nelle quali vengono solitamente applicate, permettono di ridurre il tempo di esecuzione rispetto al caso del classico algoritmo brute-force.
Uno dei problemi affrontati mediante l’utilizzo di queste tecniche algoritmiche è quello del conteggio delle inversioni.
2 Il conteggio delle inversioni¶
Il conteggio delle inversioni è un’operazione che si effettua principalmente nell’analisi dei ranking. L’obiettivo è di misurare la distanza tra due liste contenti gli stessi oggetti ma permutati tra loro (se le due liste fossero perfettamente sovrapponibili la distanza sarebbe \(0\)). Per fare ciò, viene calcolato il numero di inversioni.
2.1 Il problema¶
Si supponga di voler misurare, ad esempio, la similitudine tra i gusti musicali di due persone. Un modo per fare ciò potrebbe essere quello di chiedere loro di ordinare, in base alle proprie preferenze, una lista di \(6\) canzoni differenti. Fatto ciò, si assegna agli elementi della lista realizzata dalla prima persona un numero che va da \(1\) a \(6\), enumerando successivamente gli elementi della lista della seconda persona in accordo con gli indici della prima.
In figura sono mostrate le due liste.
Un modo per misurare la distanza tra queste due liste è quello di contare il numero di inversioni, rappresentate graficamente in figura dagli incroci tra i segmenti che collegano gli elementi delle due liste.
Nell’esempio mostrato in figura sono presenti \(3\) inversioni: \(5-2\), \(5-4\), \(3-2\) .
In termini più formali, considerando due liste ordinate:
- prima lista: \(1, 2, \dots, n\);
- seconda lista: \(a_1, a_2, \dots, a_n\),
si dirà che l’elemento i e l’elemento j sono invertiti se \(i < j\) ma \(a_i > a_j\).
Il modo più semplice per calcolare il numero di inversioni in una lista è di confrontare ogni coppia di elementi per determinare se costituiscono un’inversione o meno (secondo un approccio brute-force), per un totale di \(\frac{n(n - 1)}{2}\) operazioni di confronto. Questa operazione di confronto, tuttavia, ha una complessità totale pari a \(O(n^2)\).
Il problema da risolvere, quindi, è quello di cercare un metodo per contare il numero di inversioni presenti in una lista senza necessariamente confrontare ogni coppia di elementi.
Per fare ciò viene utilizzata la tecnica Divide et Impera.
2.2 Definizione dell’algoritmo risolutivo¶
Mediante la tecnica Divide et Impera, l’algoritmo consiste nei seguenti passi:
- la lista di partenza viene suddivisa ricorsivamente in due metà, indicate generalmente come A e B (possibilmente di uguale grandezza, pari ad \(n/2\));
- viene calcolato ricorsivamente il numero di inversioni presenti nelle due metà, A e B;
- viene calcolato il numero di inversioni presenti tra gli elementi della lista A e gli elementi della lista B;
- viene sommato il numero di inversioni, ottenendo così il totale per la lista di partenza.
Affinché l’algoritmo sia efficiente è necessario che il terzo passo, quello relativo il calcolo del numero di inversioni tra gli elementi della lista A e della lista B, abbia una complessità pari a \(O(n)\).
Per ottenere ciò si richiede che le liste A e B siano ordinate.
Questo perché, come detto prima, se le due liste non fossero ordinate il terzo passo avrebbe una complessità pari a \(O(n^2)\), dovendo confrontare tutte le coppie di elementi delle due liste per verificare se sono presenti o meno delle inversioni.
Nel caso in cui le due liste siano ordinate, invece, per calcolare le inversioni tra gli elementi \(a_i\) di A e gli elementi \(b_j\) di B basterà scorrere le due liste da sinistra verso destra, confrontando l’i-esimo elemento di A con il j-esimo elemento di B.
In questo modo si ha che:
- se \(a_i \leq b_j\), allora \(a_i\) non è invertito con nessuno degli elementi rimanenti in B;
- se \(a_i > b_j\), allora \(b_j\) è invertito con \(a_i\) e con tutti gli elementi rimanenti in A.
Effettuato questo controllo e, nel caso, incrementato il contatore delle inversioni, l’elemento più piccolo tra \(a_i\) e \(b_j\) verrà copiato in una nuova lista C ordinata, il tutto in un tempo pari a \(O(n)\).
Quello che viene fatto, dunque, altro non è che unire la tecnica Merge Sort (un algoritmo di ordinamento ricorsivo che utilizza la tecnica del Divide et Impera) all’operazione di conteggio delle inversioni.
L’implementazione dell’algoritmo di conteggio delle inversioni così definito avrà complessivamente un costo pari a \(n \; log_2 \; n\).
2.3 Algoritmo risolutivo in Python¶
In Python l’algoritmo risolutivo per il conteggio delle inversioni si realizza in due step:
- Si definisce la funzione Merge and Count che permette di fondere in maniera ordinata e, contemporaneamente, contare il numero di inversioni presenti tra gli elementi delle due liste A e B, in un tempo pari a \(O(n)\);
- Si definisce la funzione Sort and Count che permette di ordinare e contare il numero totale di inversioni presenti nella lista input, in un tempo pari a \(O(n \; log \; n)\) con \(n\) numero di elementi della lista di interesse.
Funzione MergeCount
def MergeCount(A, B):
i = 0
j = 0
C = [] # nuova lista nella quale verrano inseriti gli elementi di A e B
count = 0
while i < len(A) and j < len(B):
# se l'i-esimo elemento di A è minore del j-esimo elemento di B,
# il primo verrà inserito in C
if A[i] < B[j]:
C.append(A[i])
i += 1
# se l'i-esimo elemento di A è maggiore del j-esimo elemento di B,
# il secondo verrà inserito in C e "count" verrà incrementato di un
# numero pari ai restanti elementi in A (inversioni)
else:
C.append(B[j])
j += 1
count += len(A[i:])
# Terminato il ciclo while vengono aggiunti in C i restanti elementi di A o B
while i < len(A):
C.append(A[i])
i += 1
while j < len(B):
C.append(B[j])
j += 1
return count, C
Funzione SortCount
def SortCount(L):
# la lista input contiene un solo elemento
if len(L) == 1:
return 0, L
# la lista contiene più di un elemento, e per questa viene divisa
# in due parti sulle quali vengono applicate le funzioni
# SortCount e MergeCount (definita prima)
else:
mid = len(L) // 2
A = L[:mid]
B = L[mid:]
i = 0
j = 0
cA, A = SortCount(A)
cB, B = SortCount(B)
cL, L = MergeCount(A, B)
# numero totale di inversioni
inv = cA + cB + cL
# restituzione della soluzione del problema (numero di inversioni e
# lista ordinata)
return inv, L
2.4 Esempio¶
Un sito di incontri deve determinare la compatibilità tra i suoi iscritti. Oltre alle usuali domande riguardo età, lavoro, città di residenza e altro, agli iscritti viene chiesto di ordinare in base alle proprie preferenze una lista di 10 hobby. Karen, da poco iscritta al sito, invia le caratteristiche dell’uomo ideale che vorrebbe incontrare e la lista ordinata dei suoi hobby. In base alle caratteristiche richieste da Karen, il sito individua come possibile candidato Bob, e gli invia la lista di hobby da ordinare, per verificare che tra i due ci sia abbastanza compatibilità per metterli in contatto. Le liste compilate dai due iscritti sono le seguenti:
| N | KAREN | BOB |
| 1 | Leggere | Viaggiare |
| 2 | Andare in discoteca | Guadare film |
| 3 | Viaggiare | Cacciare |
| 4 | Ascoltare la musica | Leggere |
| 5 | Guadare film | Andare in discoteca |
| 6 | Fare jogging | Ascoltare la musica |
| 7 | Cacciare | Fare jogging |
| 8 | Cucinare | Cucinare |
| 9 | Ricamare | Giardinaggio |
| 10 | Giardinaggio | Ricamare |
La lista di Bob, rispetto a quella di Karen, risulta essere uguale a \(L = [3, 5, 7, 1, 2, 4, 6, 8, 10, 9]\). Per ottenere il numero di inversioni totali tra le due liste si stampa il risultato della funzione SortCount.
print(SortCount(L))
Il numero di inversioni totale tra le due liste risulta essere pari a 10.
