Un algoritmo semplice, ma perché funziona?

Un algoritmo semplice per un problema (apparentemente) complesso, ma per arrivarci occorre che qualcuno ci suggerisca una spiegazione comprensibile del perché funziona. Nel mondo anglosassone esiste un acronimo che fa il caso: ELI5, Explain Like I’m 5, vale a dire spiegamelo come se avessi 5 anni.
Mi ci sono imbattuto qualche giorno fa, in un articolo su Medium: “ELI5: Find the smallest positive integer value that cannot be represented as sum of any subset of a given array”.
Il problema proposto suona complicato a piacere: trovare il più piccolo intero positivo che non possa essere espresso come somma di un qualunque sottoinsieme di un insieme dato di interi positivi. L’articolo parte dalla semplificazione di assumere che l’insieme sia ordinato.
Non si perde nulla in generalità: se l’insieme non fosse ordinato, basterebbe ordinarlo prima. Utilizzando un linguaggio di programmazione, come ad esempio Python, si fa con un’unica istruzione.

Fatta questa premessa, l’unica soluzione che mi viene in mente utilizza la forza bruta:

• ricavo tutti i sottoinsiemi dell’insieme dato;
• calcolo la somma degli elementi di ciascun sottoinsieme;
• ordino le somme calcolate;
• trovo il primo buco.

Esiste però una soluzione decisamente più efficiente, con un algoritmo semplice, anzi semplicissimo. Ma capire come funziona non è immediato, a meno che qualcuno non ci fornisca una spiegazione ELI5.

Il problema

Supponiamo che l’insieme ordinato di interi positivi da cui partire sia A = [1,1,2,6]. Qual è il più piccolo intero positivo che non possa essere espresso come somma di un sottoinsieme dell’insieme dato?
Elenchiamo i possibili sottoinsiemi, sono tutti quelli costruiti a partire da 1, 2, 3 e 4 elementi:

• [1], [1], [2], [6] (somme: 1, 1, 2, 6);
• [1,1], [1,2], [1,6], [1,2], [1,6], [2,6] (somme: 2,3,7,3,7,8);
• [1,1,2], [1,1,6], [1,2,6], [1,2,6], (somme: 4, 8, 9, 9);
• [1,1,2,6], (somma: 10).

Mettiamo adesso in fila le somme trovate, eliminando i doppioni: 1, 2, 3, 4, 6, 7, 8, 9, 10. La lista è di lunghezza finita, quindi sicuramente nessun sottoinsieme può dare come somma il successivo della lista, 11. Ma c’è un buco prima, perché tra il 4 e il 6 manca il 5, che quindi è la soluzione cercata, per l’insieme A.

Un possibile algoritmo

Elencare a mente i possibili sottoinsiemi è agevole in un caso semplice come [1,1,2,6], ma la cosa si complica se la dimensione dell’insieme di partenza cresce. E anche risolvere codificando non è immediato.
Per costruire la lista dei sottoinsiemi si può ragionare, ad esempio, in modo ricorsivo. Se ho già costruito la lista per i primi N elementi dell’insieme, allora, l’aggiunta dell’elemento successivo comporta l’inserimento nella lista dell’elemento stesso, e anche di tutti i sottoinsiemi trovati in precedenza, in cui aggiungo l’elemento N+1. Ad esempio, partendo da una lista dei sottoinsiemi vuota, dovrò aggiungere via via alla lista:

• [1];
• [1], [1,1];
• [2], [1,2], [1,2], [1,1,2];
• [6], [1,6], [1,6], [1,1,6], [2,6], [1,2,6], [1,2,6], [1,1,2,6].

In tutto 15 elementi, esattamente quelli trovati con l’algoritmo ad occhio utilizzato prima.

Un modo più semplice per elencare i sottoinsiemi

La nostra lista A = [1,1,2,6] contiene 4 elementi. Nel sistema binario con 4 bit posso generare i numeri da 0000 a 1111, cioè da 0 a 15. Bene, una qualunque di queste 16 combinazioni può rappresentare un possibile sottoinsieme dell’insieme dato. In particolare, il sottoinsieme di cui fanno parte gli elementi di A in corrispondenza degli ‘1’ della combinazione.
Questa osservazione ci spiega perché i sottoinsiemi di A sono proprio 15 (non abbiamo considerato l’insieme vuoto), ma ci dice anche che, se A ha N elementi, allora i sottoinsiemi di A sono 2^N.
Si tratta di un’osservazione importante, perché indica che la complessità temporale di un algoritmo che generi i sottoinsiemi di A è dell’ordine di  2^N. Se aggiungo un elemento alla lista A, il tempo di elaborazione raddoppia.

Un possibile algoritmo

Eccoci quindi a un possibile algoritmo di forza bruta:

a = [1,1,2,6]
nbit = len(a)
ab = []
for n in range(1,2**nbit):
    b = [int(i) for i in list("{0:b}".format(n))]
    b = [0]*(nbit-len(b))+b
    ab.append(sum([x*y for x,y in zip(a,b)]))
print (set(ab))
ab = list(set(ab))
soluzione = [ab[i]+1 for i in range(len(ab)-1) if ab[i]+1 != ab[i+1] ]
if soluzione == []:
    soluzione = [ab[-1]+1]
print (soluzione[0])

Si parte dal tradurre i numeri da 1 a 2⁴ – 1 in notazione binaria su 4 bit e si utilizza questa maschera per calcolare direttamente la somma dei corrispondenti elementi presenti in ciascun sottoinsieme. Poi si mettono in fila tutte le somme calcolate e si trova il primo buco.

Si può fare di meglio, certamente. È in sostanza un esercizio di codifica, più che di programmazione, e non conosco Python così bene da essere sicuro di aver codificato efficacemente.
Devo dire comunque che una soluzione così non rende sexy il problema: il procedimento è scontato, e allora perché perdere tempo a codificarlo, visto che non si tratta di lavoro ma di piacere?

Un algoritmo semplice, ma l’idea è geniale

Ritorniamo alla lista progressiva dei possibili sottoinsiemi generata con il metodo ricorsivo, ed elenchiamo le somme dei sottoinsiemi che andiamo via via aggiungendo. Eliminando i doppioni si ha:

• 1 (lista di partenza);
• 1, 2 (aggiungo 1);
• 2, 3, 4 (aggiungo 2);
• 6, 7, 8, 9, 10 (aggiungo 6).

Ogni elemento N aggiunto (es.: 2), se la lista finora accumulata non ha buchi (nell’esempio.: 1, 2), aggiunge una sequenza di numeri interi consecutivi, a partire dal proprio valore (nell’esempio: 2, 3, 4).
Se con la lista di somme [1,2] il primo intero non presente era 3, aggiungendo [2,3,4] il successivo candidato alla soluzione diventa quindi 5.

Se ora si aggiunge il successivo (6), la lista delle somme si allunga con gli interi consecutivi: [6,7,8,9,10].
Il valore aggiunto (6) è maggiore del candidato (5) e questo genera un buco. La soluzione al nostro problema è dunque 5. Eureka!

Non è quindi necessario elaborare la lista dei possibili sottoinsiemi, ma si può semplicemente ragionare sul valore del possibile candidato alla soluzione e sul valore dell’elemento aggiunto:

• se il valore che si aggiunge (2) è minore o uguale al primo buco potenziale trovato finora (3), allora il buco potenziale si sposta a: 3 + 2 = 5;
• se il valore che si aggiunge (6) è maggiore del buco potenziale corrente (5), allora il buco rimane, ed è la soluzione cercata.

L’origine dell’acronimo ELI5 la racconta il sito Dictionary.com.
Inserito nel 2011 nell’Urban dictionary, deve la sua notorietà al sito Reddit, nel quale fu introdotto per creare una sezione in cui si potessero fare domande anche ingenue, oppure che potessero dimostrarsi non particolarmente intelligenti, mettendo chi poneva la questione al riparo da commenti salaci (o peggio).

L’algoritmo semplice, tradotto in codice

È abbastanza semplice mettere insieme il codice per realizzare l’algoritmo appena descritto. Ecco la versione Python:

a = [1,1,3,5,8,21]
maxPossible = 0
if len(a) != 0 and a[0] == 1:
    maxPossible = a[0]
    for i in range(1,len(a)):
        if a[i]> maxPossible + 1:
            break
        maxPossible += a[i]
print ('L\'intero più piccolo che non si può costruire è {}'.format(maxPossible + 1))

Nell’esempio ho utilizzato la lista di partenza proposta nell’articolo su Medium. In questo caso la soluzione è 19. Che sia un buco è immediato da verificare, perché: 21 > 1 + 1 + 3 + 5 + 8 = 18. Ma che non ce ne siano di più piccoli, beh, non è così evidente.

La logica dell’algoritmo semplice

Se spiegare perché funziona non è semplice, è invece immediato descrivere come funziona:

• la variabile maxPossible tiene traccia del massimo valore assunto dalla somma degli elementi di un possibile sottoinsieme; valore iniziale = 0;
• se la lista è vuota, oppure il primo valore della lista non è 1, allora la ricerca è finita, 1 è la soluzione;
• in caso contrario, il valore del primo elemento viene assegnato a maxPossible;
• si esplora la lista, a partire dal secondo elemento;
• si aggiorna maxPossible, aggiungendogli l’elemento corrente;
• ci si ferma quando la lista è finita, oppure quando l’elemento corrente è maggiore di maxPossible + 1.

L’algoritmo esplora la lista in modo lineare, senza utilizzare ricorsività, quindi la sua complessità è espressa come O(n). In altri termini, il tempo necessario per la sua esecuzione, nel caso peggiore, cresce linearmente con la dimensione della lista.
È un dato eccellente, come conferma l’articolo: si è visto che ricavare la lista dei sottoinsiemi di un insieme dato di n elementi ha una complessità dell’ordine di O(2ⁿ), quindi con crescita esponenziale con la dimensione della lista.

Oltre che poco sexy, quindi, la soluzione forza bruta è anche inefficiente!

Foto di apertura di Maddy Mazur da Pixabay.

Pasquale

Mi chiamo Pasquale Petrosino, radici campane, da alcuni anni sulle rive del lago di Lecco, dopo aver lungamente vissuto a Ivrea.
Ho attraversato 40 anni di tecnologia informatica, da quando progettavo hardware maneggiando i primi microprocessori, la memoria si misurava in kByte, e Ethernet era una novità fresca fresca, fino alla comparsa ed esplosione di Internet.
Tre passioni: la Tecnologia, la Matematica per diletto e le mie tre donne: la piccola Luna, Orsella e Valentina.
Potete contattarmi scrivendo a: p.petrosino@inchiostrovirtuale.it