Calcolo combinatorio - Sviluppo PDF Stampa E-mail
Scritto da Roberto Mensa   
Martedì 03 Agosto 2010 17:53
a cura di Roberto Mensa e Paolo Ardizzoni

Ho iniziato questo lavoro per sfida dopo aver letto una discussione sul NG (link).
Mi sono presto appassionato al problema: utilizzare unicamente le funzioni di Excel per lo sviluppo di disposizioni e combinazioni.

Ne sono nati un numero esagerato di file :-) vi assicuro, quello che leggerete è solo la punta di un iceberg.

In questo articolo ho raccolto quelle formule che ritengo più belle semplici e utili.

 

 

Disposizioni con ripetizione

[...]
Una presentazione ordinata di elementi di un insieme nella quale si possono avere ripetizioni di uno stesso elemento si dice disposizione con ripetizione. Cerchiamo il numero delle possibili sequenze di k oggetti estratti dagli elementi di un insieme di n oggetti, ognuno dei quali può essere preso più volte.
Ad esempio le disposizioni con ripetizione di lunghezza 2 degli elementi di {1,2,3,4,5} sono 11, 12, 13, 14, 15, 21, 22, 23, 24, 25, 31, 32, 33, 34, 35, 41, 42, 43, 44, 45, 51, 52, 53, 54, 55.
Il numero totale di disposizioni è calcolato come n^k.
Si osserva che può anche essere k > n.
[...] da
Wikipedia

Ci sono vari modi per sviluppare tutte le disposizioni in un foglio di Excel. Intanto, per comodità definiamo due nomi k e n corrispondenti alle celle dove inseriremo rispettivamente il numero di oggetti della sequenza (k) e il numero dei diversi oggetti presenti nell'insieme (n) [Come nell'esempio del file posizionarsi in A4 e digitare k nella casella del nome, posizionarsi in B4 e digitare n nella casella del nome].

 

Ottenere le disposizioni con una formula

La prima formula che propongo, restituisce le disposizioni come numeri in singole celle:
=MATR.PRODOTTO(1+RESTO(INT((RIF.RIGA(A1)-1)/(n^(RIF.COLONNA(SCARTO($A$1;;;;k))-1)));n);10^(RIF.RIGA(SCARTO($A$1;;;k))-1))
[da scrivere in una qualsiasi cella, va poi trascinata in basso]

E' una formula "meccanica" che non consuma righe in eccesso.
Trascinata oltre il numero totale di disposizioni restituisce nuovamente i valori a partire dal primo. Volendo limitare i risultati è sufficiente aggiungere una condizione all'interno di una funzione SE consentendo, a seconda dei gusti, di porre a "" a 0 o ad un valore di errore i risultati oltre i limiti ecco un esempio:

=SE(RIF.RIGA(A1)>n^k;NON.DISP();MATR.PRODOTTO(1+RESTO(INT((RIF.RIGA(A1)-1)/(n^(RIF.COLONNA(SCARTO($A$1;;;;k))-1)));n);10^(RIF.RIGA(SCARTO($A$1;;;k))-1)))

[da scrivere in una qualsiasi cella, va poi trascinata in basso]

Lasciando la formula così com'era inizialmente, potrete invece aggiungere una formattazione condizionale per mostrare i soli risultati utili [selezionare l'intero intervallo contenente le formule -> Formato -> Formattazione Condizionale ... La formula è -> =RIF.RIGA(A1)>n^k ... scegliere quindi colore del carattere bianco].

La formula è un prodotto tra due matrici la prima di una riga e k colonne, la seconda di k righe ed una colonna. Il risultato quindi è una matrice di una riga e una colonna contenente un solo valore (guardare l'help della funzione MATR.PRODOTTO).

Immagine 1
 

 

La prima matrice è la più significativa, tanto che un risultato altrettanto apprezzabile è ottenibile con la sola formula:


=1+RESTO(INT((RIF.RIGA($A1)-1)/(n^(RIF.COLONNA(A$1)-1)));n)
 

[da scrivere in una qualsiasi cella, va poi trascinata a destra e in basso]

 

Anche in questo esempio è possibile delimitare i risultati utili in vari modi. Nel file allegato utilizzo una formattazione condizionale [selezionare l'intero intervallo contenente le formule -> Formato -> Formattazione Condizionale ... La formula è -> =O(RIF.COLONNA(A$1)>k;RIF.RIGA($A2)>n^k) ... scegliendo colore del carattere bianco].

immagine 2

Gli oggetti delle serie sono contenuti singolarmente nelle celle, mancando il prodotto con la seconda matrice. 
Torniamo alla prima formula ...
Il primo argomento della funzione MATR.PRODOTTO restituisce una matrice simile ad una singola riga della tabella illustrata in immagine 2. Consideriamo ad esempio solo i k elementi della sesta riga {2;1;2;1}.
Il secondo argomento di MATR.PRODOTTO, nella formula iniziale [10^(RIF.RIGA(SCARTO($A$1;;;k))-1)] restituisce una matrice contenente le potenze successive di 10. Quindi nel caso di k=4, restituisce {1\10\100\1000}.
Il risultato finale è:
2*1+1*10+2*100+1*1000=1212 (vedi sesta riga visibile in immagine 1).

Ottenere le disposizioni con un Nome Definito
 
Per ottenere una matrice contenente tutte le righe delle disposizioni, è possibile utilizzare un nome definito. Tale nome potrà quindi sviluppare le serie se richiamato matricialmente.
Definiamo due nomi, disp_1:
=MATR.PRODOTTO(1+RESTO(INT((RIF.RIGA(SCARTO($A$1;;;n^k))-1)/(n^(RIF.COLONNA(SCARTO($A$1;;;;k))-1)));n);10^(RIF.RIGA(SCARTO($A$1;;;k))-1)) 
 
e disp_2:
=1+RESTO(INT((RIF.RIGA(SCARTO($A$1;;;n^k))-1)/(n^(RIF.COLONNA(SCARTO($A$1;;;;k))-1)));n)
[per definire i Nomi ... Inserisci->Nome->Definisci digitare i nomi e nel campo Riferito a incollare le formule]

Nelle formule ancora vengono utilizzati i nomi n e k già definiti in precedenza al solo scopo di rendere più leggibili le formule.
Una volta aggiunti i nomi è possibile richiamarli con un inserimento matriciale.
Per disp_1 selezionare un intervallo di una singola colonna sufficientemente alto (nel file di esempio F2:F1000) quindi digitare nella barra delle formule =disp_1 e confermare con Ctrl+Maiusc+Invio.
Per disp_2 selezionare un intervallo sufficientemente ampio in righe e colonne (nel file di esempio F2:N1000) quindi digitare nella barra delle formule =disp_2 e confermare con Ctrl+Maiusc+Invio.
I risultati sono visibilmente simili alle immagini 1 e 2. Una differenza è che la matrice è già correttamente dimensionata e le celle che eventualmente sono esterne, restituiranno un valore di errore #N\D!.

Disposizioni semplici (senza ripetizioni)

[...]
Una disposizione semplice di lunghezza k di elementi di un insieme di n oggetti, con k ≤ n, è una presentazione ordinata di k elementi nella quale non si possono avere ripetizioni di uno stesso oggetto.
Ad esempio le disposizioni semplici di lunghezza 2 degli elementi dell'insieme {1,2,3,4,5} sono 5!/(5-2)! = 5!/3! = 120/6 = 20: 12, 13, 14, 15, 21, 23, 24, 25, 31, 32, 34, 35, 41, 42, 43, 45, 51, 52, 53, 54.
Si osserva che le permutazioni sono casi particolari delle disposizioni semplici: le permutazioni di un insieme di n oggetti sono le disposizioni semplici di tali oggetti di lunghezza n.
[...] da
Wikipedia
 
Anche in questo caso continuiamo ad utilizzare i due nomi n e k.
Per ottenere le disposizioni in Excel è possibile utilizzare diverse formule e modi. Le formule più spinte non richiedono colonne di appoggio, sono formule matriciali complicate che però consumano molte più righe di quelle necessarie. Per questo motivo risultano più lente e limitate. In particolare esiste una formula molto bella che non utilizza nessuna colonna di appoggio ed è apprezzabile anche per la relativa velocità di calcolo. Questa formula non è citata in questo articolo per il semplice motivo che non è una formula che ho scritto io :-). Me la sono trovata tra capo e collo e non ho ancora capito se la cosa mi dispiaccia oppure mi lusinghi. Esiste! Posso giurarlo e malgrado io la conosca non è a mia saputa pubblicata da nessuna parte. Spero che i lettori più agguerriti troveranno questa segnalazione stimolante e chissà che riescano a scriverla di loro mano.
 
Ottenere le disposizioni semplici con una formula
 
La formula che propongo utilizza una colonna di appoggio contenente le disposizioni con ripetizioni. Il risultato va poi ordinato e per questo viene usata un'ulteriore colonna. Il vantaggio è quello di non consumare righe in eccesso e utilizzare formule che non necessitano di inserimenti matriciali.
Consideriamo quindi la disposizione dei dati come nel file allegato, in colonna F le disposizioni con ripetizioni a partire da F2 la formula illustrata in precedenza:
=MATR.PRODOTTO(1+RESTO(INT((RIF.RIGA(A1)-1)/(n^(RIF.COLONNA(SCARTO($A$1;;;;k))-1)));n);10^(RIF.RIGA(SCARTO($A$1;;;k))-1))
 
in colonna M, a partire da M2:
=F2*VAL.ERRORE(MODA(--STRINGA.ESTRAI(F2;RIF.RIGA(SCARTO($A$1;;;k));1)))

in colonna N a partire da N2:
=GRANDE(SCARTO($M$2;;;n^k);RIF.RIGA(A1))
 
Le tre formule vannno trascinate in basso fino a bisogno.
Per nascondere i valori in eccesso rispetto al totale di disposizioni semplici possiamo utilizzare ancora la formattazione condizionale [selezionare l'intero intervallo di colonna N contenente le formule -> Formato -> Formattazione Condizionale ... La formula è -> =RIF.RIGA(A1)>PERMUTAZIONE(n;k) ... scegliendo colore del carattere bianco].
 
immagine 3
 
 
 
La formula in colonna M è la più fignificativa, utilizza la funzione MODA per rilevare la presenza di oggetti doppi all'interno della serie. Riferendosi alla colonna delle disposizioni con ripetizioni è sufficiente quindi escludere le disposizioni in cui gli oggetti sono ripetuti. MODA restituisce il valore più ripetuto e un valore di errore qualora nessuno degli argomenti è ripetuto per più di una volta. E' proprio quello che ci serve! 
 
Un risultato simile che non utilizza la colonna di appoggio F (quella con le disposizioni con ripetizioni) si può ottenere sfruttando la stessa logica ma utilizzando RIF.RIGA. Il prezzo da pagare è il consumo di un maggior numero di righe. Vediamola ... in colonna F a partire da F2:
=(RIF.RIGA(A1)+SINISTRA("1123";k))*VAL.ERRORE(MODA(0;RIF.RIGA(SCARTO($A$1;n;;9-n));1*STRINGA.ESTRAI((RIF.RIGA(A1)+SINISTRA("1123";k));RIF.RIGA(SCARTO($A$1;;;k));1)))
in colonna E a partire da E2:
=GRANDE(SCARTO($F$2;;;STRINGA.ESTRAI("987654321";10-n;k));RIF.RIGA(A1))
[vanno poi trascinate in basso]
Per nascondere i valori in eccesso rispetto al totale di disposizioni semplici possiamo utilizzare ancora la formattazione condizionale [selezionare l'intero intervallo di colonna E contenente le formule -> Formato -> Formattazione Condizionale ... La formula è -> =RIF.RIGA(A1)>STRINGA.ESTRAI("987654321";10-n;k)-SINISTRA("1123";k) ... scegliendo colore del carattere bianco].
Mentre la prima soluzione ha come limite il numero di disposizioni con ripetizioni, questa seconda soluzione è limitata dal numero di righe (seppur utilizzando qualche accorgimento per diminuirne il consumo) presente in un foglio di calcolo. Abbiamo visto che le disposizioni con ripetizioni non consumavano righe in eccesso, quindi sicuramente una colonna di appoggio in più è ampiamente sacrificabile considerato che ne rimangono ancora molte :-)
 
Ho scritto diverse altre formule. Soluzioni *meccaniche* per disposizioni con serie di solo due elementi (k=2), formule per nomi e tante altre. Ma quello che veramente manca in questa trattazione è la formula senza colonna di appoggio. Una a dirla tutta l'avrei ... ma è veramente bruttina, quindi come già anticipato, lascio a voi l'onore e la magia di scriverla.
 

Combinazioni semplici (senza ripetizioni)

[...]
Si chiama combinazione semplice una presentazione di elementi di un insieme nella quale non ha importanza l'ordine dei componenti e non si può ripetere lo stesso elemento più volte.
Ad esempio le combinazioni semplici di lunghezza 4 degli elementi di {1,2,3,4,5,6} sono 6!/(4!2!) = 15: 1234, 1235, 1236, 1245, 1246, 1256, 1345, 1346, 1356, 1456, 2345, 2346, 2356, 2456, 3456.
[...] da
Wikipedia

Per le combinazioni propongo due soluzioni.
La prima utilizza distintamente i nomi disp_1 e disp_2 (definiti in precedenza). La seconda è una formula che compie il lavoro in piena autonomia, senza necessità di alcun *appoggio*. Quest'ultima basterebbe a soddisfare qualsiasi esigenza. E' sicuramente la più bella sopratutto per la semplicità. Le soluzioni che usano un nome definito, sono proposte in questo articolo perchè si basano su un algoritmo comunque interessante che offre una valida alternativa qualora si disponga, nello stesso foglio,  delle disposizioni con ripetizione.

Iniziamo con le combinazioni che utilizzano i nomi già discussi disp_1 e disp_2.
Formula che utilizza il nome disp_1:

=PICCOLO(SE(FREQUENZA(MATR.PRODOTTO(10^STRINGA.ESTRAI(disp_1;RIF.COLONNA(SCARTO($A$1;;;;k));1);RIF.RIGA(SCARTO(D1;;;k))^0);MATR.PRODOTTO(10^STRINGA.ESTRAI(disp_1;RIF.COLONNA(SCARTO($A$1;;;;k));1);RIF.RIGA(SCARTO($A$1;;;k))^0))=FATTORIALE(k);disp_1);RIF.RIGA(A1))

[da scrivere in una qualsiasi cella, va poi trascinata in basso]

Formula che utilizza il nome disp_2:

=PICCOLO(SE(FREQUENZA(MATR.PRODOTTO(10^disp_2;RIF.RIGA(SCARTO($A$1;;;k))^0);MATR.PRODOTTO(10^disp_2;RIF.RIGA(SCARTO($A$1;;;k))^0))=FATTORIALE(k);MATR.PRODOTTO(disp_2;10^(RIF.RIGA(SCARTO($A$1;;;k))-1)));RIF.RIGA(A1))

[da scrivere in una qualsiasi cella, va poi trascinata in basso]

queste formule sfruttano la caratteristica che le combinazioni sono disposizioni semplici degli stessi elementi prese una sola volta (non essendo importante l'ordine dei componenti) consideriamo ad esempio le due disposizioni 1;2 e 2;1, entrambe identificano la combinazione dell'elemento 1 con il 2. Notiamo che: 10^1+10^2=10^2+10^1 quindi in sostanza le disposizioni 12 e 21 sottoposte a questo calcolo restituiscono entrambe il risultato 120 ... sottoponiamo quindi tutte le disposizioni a questo procedimento. Quante sono le disposizioni semplici che identificano una stessa combinazione? Semplicemente disposizioni semplici/combinazione ovvero fattoriale di k. La struttura di entrambe le formule sfrutta FREQUENZA per estrarre i valori unici delle disposizioni, che sottoposte al calcolo descritto, restituiscono lo stesso risultato fattoriale(k) volte. Questo lavoro viene svolto sulle disposizioni con ripetizione. Il risultato rimane invariato visto che le disposizioni che non sono combinazioni avranno una frequenza diverse da fattoriale di k.

Veniamo ora alla funzione che non usa appoggio di alcun tipo:

=PICCOLO(SE((MATR.PRODOTTO(--((RESTO(INT((RIF.RIGA(SCARTO($A$1;;;n^k))-1)/(n^(RIF.COLONNA(SCARTO($A$1;;;;k-1))-1)));n))<(resto(int((rif.riga(scarto($a$1;;;n^k))-1)/(n^(rif.colonna(scarto($b$1;;;;k-1))-1)));n)));rif.riga(scarto($a$1;;;k-1))^0)=(k-1));(matr.prodotto(1+resto(int((rif.riga(scarto($a$1;;;n^k))-1)/(n^(rif.colonna(scarto($a$1;;;;k))-1)));n);0,1^(rif.riga(scarto($a$1;;;k))-k))));rif.riga(a1))

[da scrivere in una qualsiasi cella, va poi trascinata in basso]

immagine 4

 

Il ragionamento in questo caso è ancora più semplice. Abbiamo detto che esistono fattoriale di k disposizioni semplici che identificano una analoga combinazione. Come fare a sceglierne una sola? Semplicemente scegliendo solo quelle in cui gli oggetti risultano ordinati in un determinato modo. La lampadina mi si è accesa leggendo la definizione di combinazione riportata da Wikipedia, in particolare leggendo:
"Di solito tra le diverse disposizioni semplici di una classe si sceglie come combinazione rappresentativa la sequenza nella quale i componenti compaiono in ordine crescente" ... Quindi in sostanza consideriamo le due disposizioni 1;2 e 2;1 è sufficiente scegliere quella in cui gli oggetti sono ordinati in modo crescente ovvero 1;2. Da un insieme delle disposizioni con ripetizione (ottenibili come visto in modo *meccanico* senza consumo di righe in eccesso) il ragionamento è identico solo l'insieme è un po' più grande. Rimane il fatto che una disposizione del tipo 1;1;2 (disposizione con ripetizione dell'elemento 1) non è una combinazione perchè non è vera la disuguaglianza 1<1<2, mentre="" nella="" disposizione="" la="" disuguaglianza="" 3="" confrontare="" il="" modo="" semplice="" in="" excel="" ovvero="" i="" primi="" k-1="" oggetti="" con="" gli="" ultimi="" oggetti.="" formula="" che="" le="" disposizioni="" nel="" io="" chiamo="" font="">

RESTO(INT((RIF.RIGA(SCARTO($A$1;;;n^k))-1)/(n^(RIF.COLONNA(SCARTO($A$1;;;;k))-1)));n)
può essere modificata facilmente per ottenere questo risultato lavorando sulla sola parte evidenziata:
 
SCARTO($A$1;;;;k-1)
SCARTO($B$1;;;;k-1)

per il resto è sufficiente verificare che i confronti (fatti col <) che="" font=""><(resto(int((rif.riga(scarto($a$1;;;n^k))-1)/(n^(rif.colonna(scarto($b$1;;;;k-1))-1)));n)));rif.riga(scarto($a$1;;;k-1))^0)=(k-1));(matr.prodotto(1+resto(int((rif.riga(scarto($a$1;;;n^k))-1)/(n^(rif.colonna(scarto($a$1;;;;k))-1)));n);0,1^(rif.riga(scarto($a$1;;;k))-k))));rif.riga(a1))<1<2, mentre="" nella="" disposizione="" la="" disuguaglianza="" 3="" confrontare="" il="" modo="" semplice="" in="" excel="" ovvero="" i="" primi="" k-1="" oggetti="" con="" gli="" ultimi="" oggetti.="" formula="" che="" le="" disposizioni="" nel="" io="" chiamo="" font="">k-1.

Queste spiegazioni hanno lo scopo di illustrare l'idea che ha condotto alla scrittura delle formule. Una valutazione più approfondita utilizzando gli strumenti di debug offerti da Excel (Valuta Formula e il tasto F9) rimane necessaria a chi volesse veramente carpirne il funzionamento. In allegato a questa pagina trovate i file che contengono le diverse soluzioni illustrate.

Ho iniziato questo lavoro con l'intento di trovare UNA soluzione al problema. Lo concludo con la convinzione che ce ne sono molte. Io ne ho illustrate alcune, molte rimangono nei file su cui ho lavorato, tante altre sono ancora da scoprire. Chi volesse misurarsi col problema ha sicuramente ancora di che divertirsi, quindi ... in bocca al lupo :-)

 

 

Ricordo che a questa pagina trovate alcune soluzioni in VBA.

 

 
Nota: questo articolo è una copia autorizzata dall'autore. L'originale (eventualmente più aggiornato) si trova all'indirizzo: http://sites.google.com/site/e90e50/user/calcolo-combinatorio
 
  • combinazioni_nome_1.xls il 12/lug/2010 12.49 da roberto mensa (versione 1)
    168 k Scarica
  • combinazioni_nome_2.xls il 12/lug/2010 12.49 da roberto mensa (versione 1)
    73 k Scarica
  • combinazioni_senza_appoggio.xls il 12/lug/2010 11.36 da roberto mensa (versione 3 / versioni precedenti)
    1706 k Scarica
  • disposizioni_con_ripetizioni_formule.xls il 09/lug/2010 13.47 da roberto mensa (versione 3 / versioni precedenti)
    544 k Scarica
  • disposizioni_con_ripetizioni_nome_disp_1.xls il 12/lug/2010 16.44 da roberto mensa (versione 1)
    165 k Scarica
  • disposizioni_con_ripetizioni_nome_disp_2.xls il 12/lug/2010 16.44 da roberto mensa (versione 1)
    314 k Scarica
  • disposizioni_semplici_formule.xls il 09/lug/2010 18.24 da roberto mensa (versione 3 / versioni precedenti)
    1677 k Scarica
Ultimo aggiornamento Domenica 12 Dicembre 2010 09:58