PDA

Visualizza la versione completa : [ALGORITMO] Trovare tutte le combinazioni di N elementi


ing82
18-03-2018, 19:05
Sono parecchio in difficoltà :dhò: nel riuscire a trovare l'algoritmo che mi permetta di trovare tutte le combinazioni di n elementi, che però possono essere tra loro esclusivi, nel senso che la presenza dell'i-esimo elemento esclude la presenza del j-esimo elemento sulla base di una matrice detta di contemporaneità, simmetrica.
Faccio un esempio, potrebbero essere gli elementi V1, W1, T1, V2, W2, T2, e la matrice di contemporaneità sia





V1
W1
T1
V2
W2
T2


V1
-
1
1
0
1
1


W1
1
-
1
1
0
1


T1
1
1
-
1
1
0


V2
0
1
1
-
1
1


W2
1
0
1
1
-
1


T2
1
1
0
1
1
-




L'elemento mij della matrice sta quindi a dire se l'elemento della colonna j puo' essere presente contemporaneamente all'elemento della riga i.

Dalla prima riga, si ricava che le combinazioni possibili sono le seguenti quattro:




V1
W1
T1
V2
W2
T2


01
1
1
1
0
0
0


02
1
1
0
0
0
1


03
1
0
1
0
1
0


04
1
0
0
0
1
1




e così via...

Il tentativo è stato:
- fisso presente un elemento, (a turno nell'ordine uno ciascuno degli elementi)
- poi fisso presente un secondo elemento, a turno uno ciascuno degli elementi della riga diversi da zero
- poi scorro tutti gli elementi della riga e verifico se ciascuno può essere presente o meno con gli elementi già considerati presenti nella combinazione.

Con questo modo di operare, con l'esempio qui riportato, perdo per strada la combinazione 04, quindi questo modo di procedere non e' corretto, ma non riesco a vedere altre strade.
Non ci sono limiti a quanti elementi un elemento puo' contemporaneamente escludere.
Suggerimenti?

Scara95
22-03-2018, 04:34
C'è qualcosa che mi sfugge, stai considerando solamente le combinazioni di lunghezza 3? Perché altrimenti le combinazioni che comprendono V1 dovrebbero essere [[1,0,0,0,5,6],[1,2,0,0,0,6],[1,0,0,0,0,6],[1,0,3,0,5,0],[1,0,0,0,5,0],[1,2,3,0,0,0],[1,0,3,0,0,0],[1,2,0,0,0,0],[1,0,0,0,0,0]]

ing82
22-03-2018, 11:49
C'è qualcosa che mi sfugge, stai considerando solamente le combinazioni di lunghezza 3? Perché altrimenti le combinazioni che comprendono V1 dovrebbero essere [[1,0,0,0,5,6],[1,2,0,0,0,6],[1,0,0,0,0,6],[1,0,3,0,5,0],[1,0,0,0,5,0],[1,2,3,0,0,0],[1,0,3,0,0,0],[1,2,0,0,0,0],[1,0,0,0,0,0]]

Grazie Scara95 per l'interessamento, giusta osservazione.
Ho considerato solo le combinazioni di lunghezza tre perche' questa porzione del problema sottintende le possibili combinazioni con presenti tutti i possibili elementi, rispettando la matrice di contemporaneità.

Credo a questo punto valga la pena illustrare il problema generale di cui fa parte il quesito posto, perche' piu' ci penso, piu' vedo che l'unica strada e' generare tutte le combinazioni, e durante il processo, verificare che ciascuna nuova combinazione creata rispetti anche i vincoli dettati dalla matrice di contemporaneità.

Il problema generale e' trovare le combinazioni di n elementi, ciascuno dei quali puo' assumere un valore da scegliere tra una lista di valori possibili per ciascun elemento.
Tra questi elementi, ce ne puo' essere uno che se appartiene ad una determinata categoria, risulta sicuramente presente col suo valore massimo, mentre gli altri potranno continuare ad essere combinati tra loro in modo 'normale', rispettando pero' i vincoli forniti dalla matrice di contemporaneita'.
Per gli elementi appartenenti sempre alla medesima categoria, per qualcuno potrebbe essere necessario considerare l'effetto segno.

Provo a fare un esempio, abbastanza semplice, perche' il numero di combinazioni altrimenti sale troppo rapidamente:
elemento G1, coefficienti possibili 1.0 e 1.3;
elemento G2, coefficienti possibili 0.0 e 1.5;
elemento V1, coefficienti possibili -1.5 e 1.5 (se non considerassi l'effetto segno sarebbero 0.0 e 1.5); quano T1 o T2 sono principali, i coefficienti diventano -0.6, 0.0 e 0.6;
elemento T1, coefficienti possibili 0.0 e 1.5; quando V1 e' principale, i coefficienti diventano 0.0 e 0.9;
elemento T2, coefficienti possibili 0.0 e 1.5; quando V1 e' principale, i coefficienti diventano 0.0 e 0.9;

La matrice di contemporaneità in un caso del genere fornirebbe le indicazioni per dire che T1 e T2 possono essere presenti con V1, ma non contemporaneamente, cioe' T1 esclude T2 e viceversa.
Gli elementi che possono essere considerati come principali in questo caso sono V1, T1 e T2

Dovrebbero uscire le seguenti combinazioni [G1, G2, V1, T1, T2]:
V1 considerato principale, quindi valore costante prima 1.5 e poi -1.5 (possibile l'assenza contemporanea di T1 e T2, ma non la presenza contemporanea)
[1.0, 0.0, 1.5, 0.0, 0.0]
[1.0, 0.0, 1.5, 0.0, 0.9]
[1.0, 0.0, 1.5, 0.9, 0.0]
[1.0, 1.5, 1.5, 0.0, 0.0]
[1.0, 1.5, 1.5, 0.0, 0.9]
[1.0, 1.5, 1.5, 0.9, 0.0]
[1.3, 0.0, 1.5, 0.0, 0.0]
[1.3, 0.0, 1.5, 0.0, 0.9]
[1.3, 0.0, 1.5, 0.9, 0.0]
[1.3, 1.5, 1.5, 0.0, 0.0]
[1.3, 1.5, 1.5, 0.0, 0.9]
[1.3, 1.5, 1.5, 0.9, 0.0]
[1.0, 0.0, -1.5, 0.0, 0.0]
[1.0, 0.0, -1.5, 0.0, 0.9]
[1.0, 0.0, -1.5, 0.9, 0.0]
[1.0, 1.5, -1.5, 0.0, 0.0]
[1.0, 1.5, -1.5, 0.0, 0.9]
[1.0, 1.5, -1.5, 0.9, 0.0]
[1.3, 0.0, -1.5, 0.0, 0.0]
[1.3, 0.0, -1.5, 0.0, 0.9]
[1.3, 0.0, -1.5, 0.9, 0.0]
[1.3, 1.5, -1.5, 0.0, 0.0]
[1.3, 1.5, -1.5, 0.0, 0.9]
[1.3, 1.5, -1.5, 0.9, 0.0]
T1 considerato come principale, quindi con valore costante 1.5 (tutti i T2 sono zero perche' esclusi dalla matrice di contemporaneita')
[1.0, 0.0, -0.6, 1.5, 0.0]
[1.0, 0.0, 0.0, 1.5, 0.0]
[1.0, 0.0, 0.6, 1.5, 0.0]
[1.0, 1.5, -0.6, 1.5, 0.0]
[1.0, 1.5, 0.0, 1.5, 0.0]
[1.0, 1.5, 0.6, 1.5, 0.0]
[1.3, 0.0, -0.6, 1.5, 0.0]
[1.3, 0.0, 0.0, 1.5, 0.0]
[1.3, 0.0, 0.6, 1.5, 0.0]
[1.3, 1.5, -0.6, 1.5, 0.0]
[1.3, 1.5, 0.0, 1.5, 0.0]
[1.3, 1.5, 0.6, 1.5, 0.0]

T2 considerato come principale, quindi con valore costante 1.5
[1.0, 0.0, -0.6, 0.0, 1.5]
[1.0, 0.0, 0.0, 0.0, 1.5]
[1.0, 0.0, 0.6, 0.0, 1.5]
[1.0, 1.5, -0.6, 0.0, 1.5]
[1.0, 1.5, 0.0, 0.0, 1.5]
[1.0, 1.5, 0.6, 0.0, 1.5]
[1.3, 0.0, -0.6, 0.0, 1.5]
[1.3, 0.0, 0.0, 0.0, 1.5]
[1.3, 0.0, 0.6, 0.0, 1.5]
[1.3, 1.5, -0.6, 0.0, 1.5]
[1.3, 1.5, 0.0, 0.0, 1.5]
[1.3, 1.5, 0.6, 0.0, 1.5]

Alla luce di quanto illustrato, avendo gia' ottenuto il modo per trovare tutte le combinazioni possibili, credo che il modo piu' semplice sia aggiungere un controllo alla combinazione trovata se rispetti i vincoli dati dalla matrice di contemporaneità, e quindi decidere se tenerla o scartarla.

Non vedo altre strade...

Grazie di nuovo per l'interessamento, e ovviamente, se esiste una strada migliore, pronto a percorrerla.
Grazie

ing82
22-03-2018, 16:03
dato che la risposta che ho postato non risulta visibile, mi permetto di mandare questa risposta, anche se inutile...
scusate

Loading