[excel] Dati N elementi scrivere tutte le combinazioni con ripetizioni possibili

Partiamo da un problema semplice. Dati N elementi vogliamo trovare con Excel tutte le combinazioni possibili, tenendo conto delle ripetizioni e del fatto che l’ordine non conti (in matematica si parlerebbe di combinazioni con ripetizioni). 

Ammettiamo per esempio di avere 3 elementi: A, B e C. Da questi 3 elementi possiamo ottenere 10 combinazioni con ripetizioni in totale: AAB, AAC, ABB, ABC, ACC, BBB, BBC, BCC, CCC, AAA

Notiamo che non sono presenti combinazioni come ABA oppure BAA che sono equivalenti a AAB, dal momento che l’ordine non conta.

Vediamo adesso come generare questi dati in Excel. Per motivi computazionali limiteremo l’esercizio ad un massimo di 6 elementi.

Anzitutto scriviamo i nostri elementi, noi lo faremo nel modo seguente partendo dalla cella N1.

In questo modo abbiamo creato un riferimento numerico (N2:N7) con gli oggetti che vogliamo combinare (O2:O7).

Adesso vogliamo scrivere le combinazioni a partire dagli elementi numerici, mettendo in colonne i singoli valori combinati. Anzitutto scriveremo tutte le combinazioni in colonne. Partendo da questo presupposto nella prima colonna il primo valore si ripeterà N^(N-1) volte. Se avessimo N = 2 il primo elemento si ripeterebbe solo 2 volte, se avessimo N = 3 il primo elemento si ripeterebbe per 9 volte ecc. Il secondo elemento si ripeterà N^(N-2) volte e così via per le colonne successive.

Spostiamoci in A1 e digitiamo quindi la seguente formula:

=SE(RIF.COLONNA()<=CONTA.VALORI($O:$O)-1;SE(RIF.RIGA()<=POTENZA(CONTA.VALORI($O:$O)-1;CONTA.VALORI($O:$O)-1);(RESTO(ARROTONDA.PER.DIF(RIF.RIGA()/(POTENZA(CONTA.VALORI($O:$O)-1;CONTA.VALORI($O:$O)-1-RIF.COLONNA()));0);CONTA.VALORI($O:$O)-1)+1);"");"")

Con il SE verifichiamo se mostrare o meno i valori in base alla quantità di elementi inseriti. Ricordiamoci che vogliamo sviluppare l’esercizio per un massimo di 6 elementi possibili.

Espandiamo la formula sulle colonne A:F, per ridurre l’impatto sulle prestazioni possiamo inserire la formula solo in A1:F52000 in modo da coprire il massimo numero di combinazioni possibili (6*6^5 = 46.656).

Fatto questo abbiamo generato tutte le combinazioni possibili con gli elementi dati.

Adesso vogliamo contare le ripetizioni. Per farlo distribuiamo i 6 parametri in altrettante colonne e per ogni riga contiamo quante volte appare il parametro. Se avessimo ABC come valori, allora la combinazione AAB corrisponderebbe ad un codice tipo 210, dove 2 è il numero di volte di A, 1 quelle di B e 0 quelle di C. Nello stesso esempio ABA = 210 e AAC = 201 ecc.

Posizioniamoci quindi in G1 e scriviamo:

=CONTA.SE($A1:$F1;RIF.COLONNA()-6)

Espandiamo la formula su G1:l52000.

Per comodità in M1 scriviamo le 6 colonne concatenate usando:

=G1&H1&I1&J1&K1&L1

Espandiamo la formula su M1:M52000.

In R1 traduciamo i numeri nei valori che abbiamo scelto come oggetti usando:

=SE.ERRORE(CERCA.VERT(A1;$N$1:$O$7;2;FALSO);"")&SE.ERRORE(CERCA.VERT(B1;$N$1:$O$7;2;FALSO);"")&SE.ERRORE(CERCA.VERT(C1;$N$1:$O$7;2;FALSO);"")&SE.ERRORE(CERCA.VERT(D1;$N$1:$O$7;2;FALSO);"")&SE.ERRORE(CERCA.VERT(E1;$N$1:$O$7;2;FALSO);"")&SE.ERRORE(CERCA.VERT(F1;$N$1:$O$7;2;FALSO);"")

E infine in Q1 estraiamo solo le combinazioni univoche, utilizzando:

=SE(CONTA.SE($M$1:M1;M1)<2;R1;"")

Contiamo cioè se la combinazione corrente è presente 2 o più volte nelle combinazioni precedenti. Se lo è non la mostriamo (è già stata mostrata!) altrimenti la mostriamo.

Espandiamo tutto fino alla riga 52000.

Infine verifichiamo il tutto inserendo in N9 il conteggio dei valori trovati:

{=SOMMA(SE(LUNGHEZZA(Q:Q)=CONTA.VALORI(O:O)-1;1;0))}

Attenzione! Le parentesi graffe sottintendono il calcolo matriciale, per cui per eseguire la formula bisogna farlo premendo CTRL+SHIFT+INVIO.

E in N11 inseriamo il valore teorico datoci dal calcolo combinatorio rispetto al numero di oggetti interessati:

=FATTORIALE(2*(CONTA.VALORI(O:O)-1)-1)/(FATTORIALE(CONTA.VALORI(O:O)-1)*FATTORIALE(CONTA.VALORI(O:O)-2))

Se tutto è andato bene nella colonna Q otteniamo le combinazioni filtrate che desideravamo.

Per completezza qui si può scaricare il file excel con l’esercizio svolto.

Rispondi

%d blogger hanno fatto clic su Mi Piace per questo: