Calcolo combinatorio - Sviluppo |
![]() |
![]() |
![]() |
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). 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
[...] 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:
[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 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].
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)
[...]
Per le combinazioni propongo due soluzioni.
Iniziamo con le combinazioni che utilizzano i nomi già discussi disp_1 e disp_2. =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] =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] 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]
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: 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
|
Ultimo aggiornamento Domenica 12 Dicembre 2010 09:58 |