[Algoritmo Java] combinazioni di coppie

[guylmaster]

Salve a tutti,
devo progettare un piccolo algoritmo, da realizzare in java, che però mi sta facendo scervellare.

Mettiamo che io ho un insieme formato da K nodi e devo calcolarmi le combinazioni di nupple di questi K nodi, mi speigo meglio:

Se ho K= 1 ovvero un solo nodo X1 ed ho N=2 quindi sono delle coppie, io devo crearmi (considerando anche il caso non ho quel nodo):

({},{})
({X1},{}), ({},{X1})
({X1},{X1})

Da notare che: Ho bisogno che le combinazioni di coppie siano ordinate, al livello 0 ho solo 0 nodi su entrambe le coppie, al livello in totale 1 solo nodo e così via. Ovviamente il tutto mi serve generalizzato per qualsiasi K e qualsiasi N.

Voi cosa consigliereste di fare?

La strada che stavo prendendo, ma in cui mi sto incasinando, è di calcolarmi l'insieme delle parti dell'insieme di inizio e poi calcolarmi tutte le possibili combinazioni di coppie andando ad aggiungere un nodo per volta.

Vi ringrazio in anticipo per la pazienza,
guylmaster.

[Daniels118]

Prima di tutto creerei una copia dell'insieme dei nodi e vi aggiungerei degli elementi vuoti fino ad avere almeno N elementi, in modo da poter eliminare la singolarità.

Ora, immagina che il risultato del tuo algoritmo sia un insieme di numeri. Ciascuno di questi numeri è la combinazioni di N cifre. Le cifre non sono le classiche da 0 a 9, ma provengono dall'insieme dei nodi. Ora non devi far altro che contare.

Chiamiamo T il numero totale di nodi (inclusi eventuali valori nulli):
T = MAX(K, N)

Chiamiamo V l'insieme dei nodi ed R l'insieme dei risultati.
//Prepara gli indici per selezionare i nodi
Array indici[N];
for i = 0; i < N; i++ {
indici[i] = 0;
}
while (indici[N-1] < K) {
//Crea la tupla prendendo i nodi secondo i valori degli indici
Array tupla[N];
for i = 0; i < N; i++ {
tupla[i] = V[indici[i]];
}
//Inserisce la tupla nei risultati
R.push(tupla);
//Aggiorna gli indici
indici[0]++;
for (i = 0; i < N; i++) {
if (indici[i] == T && i < N - 1) {
indici[i] = 0;
indici[i + 1]++;
} else {
break;
}
}
}
Probabilmente va affinata un po', ma aspetto di sentire cosa ne pensi.

[guylmaster]

Prima di tutto creerei una copia dell'insieme dei nodi e vi aggiungerei degli elementi vuoti fino ad avere almeno N elementi, in modo da poter eliminare la singolarità.

Ora, immagina che il risultato del tuo algoritmo sia un insieme di numeri. Ciascuno di questi numeri è la combinazioni di N cifre. Le cifre non sono le classiche da 0 a 9, ma provengono dall'insieme dei nodi. Ora non devi far altro che contare.

Chiamiamo T il numero totale di nodi (inclusi eventuali valori nulli):
T = MAX(K, N)

Chiamiamo V l'insieme dei nodi ed R l'insieme dei risultati.
//Prepara gli indici per selezionare i nodi
Array indici[N];
for i = 0; i < N; i++ {
indici[i] = 0;
}
while (indici[N-1] < K) {
//Crea la tupla prendendo i nodi secondo i valori degli indici
Array tupla[N];
for i = 0; i < N; i++ {
tupla[i] = V[indici[i]];
}
//Inserisce la tupla nei risultati
R.push(tupla);
//Aggiorna gli indici
indici[0]++;
for (i = 0; i < N; i++) {
if (indici[i] == T && i < N - 1) {
indici[i] = 0;
indici[i + 1]++;
} else {
break;
}
}
}
Probabilmente va affinata un po', ma aspetto di sentire cosa ne pensi.

Ad essere sincero non sto riuscendo a capirlo, magari complice del fatto che ci sto sbattendo su la testa da un pò e sono fuso. Potresti aggiungere qualche spiegazione/commento perfavore?

[guylmaster]

Sto provando a fare dei trace per capire meglio, inanzi tutto la storia delle singolarità non l'ho capita.

Se io ho:

K(nodi) = |{vuoto,X1,X2}| = 3
N(epoche) = 3
T = MAX(K,N) = 3 (non ho capito perchè questo max sinceramente)
V(insieme delle parti) = {{vuoto}, {X1}, {X2}, {X1,X2}}

Allora al primo passo ho
indici = [0,0,0]
tupla = [vuoto,vuto,vuoto]
aggiorono indici = [1,0,0]

Al secondo passo ho
indici = [1,0,0]
tupla = [X1,vuto,vuoto]
aggiorono indici = [2,0,0]

Al terzo passo ho
indici = [2,0,0]
tupla = [X2,vuto,vuoto]
aggiorono indici = [3,0,0]
quindi indici[1] == 3, i=0 < N(3)-1 allora riaggiorno gli indici ovvero:
indici = [0,1,0]

Al quarto passo ho
indici = [0,1,0]
tupla = [vuoto,X1,vuoto]
aggiorono indici = [1,1,0]


Al quinto passo c'è qualcosa che non va perchè ho:
indici = [1,1,0]
tupla = [X1,X1,vuoto]
..


Ovvero ho creato le tuple:
[vuoto,vuto,vuoto], [X1,vuto,vuoto], [X2,vuto,vuoto], [vuoto,X1,vuoto] e all'ultimo passo dove mi aspettavo [vuoto,X2,vuoto] ottengo invece [X1,X1,vuoto]!

Cosa mi sfugge?
Non capisco nemmeno perchè nell'ultimo ciclo ho in AND "i < N - 1".


EDIT: Per capirci meglio, quello che mi aspetto se ho 3 nodi, ovvero vuoto, 1 e 2, ed ho 2 epoche è: (ovviamente non sto a scrivere tutto fino alla fine)

level0: ({}, {})
level1: ({1}, {}); ({2}, {}); ({}, {1}); ({}, {2})
level2: ({1,2}, {}); ({1}, {1}); ({1}, {2}); ({2}, {1}); ({2}, {2}); ({}, {1,2});
[..]

[Daniels118]

Il tuo problema è contagioso, mi sto incasinando anch'io... ho riletto il tuo primo post rendendomi conto di aver interpretato male la tua richiesta.
Ora che pensavo di aver capito, ho letto l'ultimo post e mi sono reso conto che ho toppato di nuovo, questa cosa mi ha spiazzato: ({1,2}, {})
Temo che avrò bisogno di qualche ulteriore delucidazione.
Per curiosità, a cosa ti serve?

[guylmaster]

Il tuo problema è contagioso, mi sto incasinando anch'io... ho riletto il tuo primo post rendendomi conto di aver interpretato male la tua richiesta.
Ora che pensavo di aver capito, ho letto l'ultimo post e mi sono reso conto che ho toppato di nuovo, questa cosa mi ha spiazzato: ({1,2}, {})
Temo che avrò bisogno di qualche ulteriore delucidazione.
Per curiosità, a cosa ti serve?

Si forse se ti spiego meglio cosa sto facendo riusciamo meglio (anche se mi sembra che comunque tu sia arrivato molto vicino alla soluzione).

L'idea è che ho K variabili {X1,X2,..,Xk} che possono o meno influenzare una variabile Y, il tutto su N epoche e ho bisogno di rappresentare in qualche modo lo spazio di ricerca.

Lo spazio di ricerca lo rappresento quindi come un diagramma di Hasse (in realtà questo a livello teorico, praticamente credo ficcherò tutto in delle matrici) dove al livello 0, la radice, ho N insieme vuoti ({},..,{}).

Da notare che il numero di variabili totali al livello 0 è pari a 0. Al livello 1, ovvero nei discendenti della radice posso avere, su tuttti gli insiemi, un totale di 1 sola variabile. Devo quindi fare tutte le combinazioni di assegnazioni delle variabili ma in totale su tutte le epoche ne posso avere al massimo 1.
Ecco se immagino le variabili X1, X2 ed N=2 per semplicità allora avro come radice:

({}{}) al livello 0

Al livello 1 che discendenti posso avere del nodo radice ({}{}) per fare in modo che il massimo numero di variabili, in totale sui due insiemi, sia pari ad 1?
bene potrò avere:

({X1}, {}); ({X2}, {}); ({}, {X1}); ({}, {X2})

Ora prendendo singolarmente ogni nodo del livello1 vado a generare i discendenti (contando che non è un albero ma un diagramma di hasse, ovvero un nodo può avere più genitori) al livello 2. Questo vuol dire che in totale posso avere 2 variabili sui due insiemi.

Se prendo ({X1}, {}) come creo i discendenti di livello 2? faccio tutte le combinazioni aggiungendo però al masismo una variabile, ovvero i suoi dicendenti saranno:

({X1}, {X1}), ({X1}, {X2}) ({X1,X2}, {})

e cosi via per tutti i nodi. Da notare sempre che al livello 2 il totale di di variabili, sui due insiemi, per ogni nodo è 2. Al livello 3 saranno 3 e così via finchè non arriviamo ad un nodo finale in cui ci saranno tutte le variabili messe assieme.

Una proprietà importante che ti voglio far notare è che un diagramma di Hasse è tale perchè definisce un ordinamento, qui l'ordinamento è data da una funzione di contenimento tra "genitori e figli" tale che
({X1}, {X1}) è discendete di ({X1}, {}) perchè

{X1} è contenuto in {X1} AND {} è contenuto in {X1}


Ad esempio ({X2}, {X1}) non è discendente di ({X1}, {}) perchè {X1} non è contenuto in {X2}, più in generale:


ni = (S1i,S2i) C nj = (S1j,S2j) solo se S1i C S1j AND S21 C s2j

Quindi in pratica quello che sto creando è un diagramma di Hasse su cui la funzione di ordinamento è questa "speciale" funzione di contenimento su due insiemi.
Qui puoi trovare una descrizione di cos'è un diagramma di hasse se vuoi darti una rinfrescata:
http://en.wikipedia.org/wiki/Hasse_diagram

Spero di essere stato più chiaro e che ti abbia contagiato abbastanza da continuare ad aiutarmi, magari l'algoritmo che mi hai passato con qualche piccola modifichina raggiunge lo scopo!

Edit: In pratica partendo dalla radice (continuo a sottolineare che non è propriamente un albero) ({},{}) devo creare i figli aggiungendo una sola variabile e quindi creo tutte le combinazioni, aggiungo X1 al primo insieme e il secondo rimane vuoto e creo la tupla ({X1},{}), l'aggiungo al secondo insieme e il primo rimane vuoto e creo un altra tupla ({},{X1}), poi passo ad aggiungere X2 e creo ({X2},{}) e ({}{X2}). Il tutto aggiungendo 1 variabile per combinazione. Poi al livello successivo creeo i figli di ogni nodo aggiungendo sempre 1 sola variabile e cosi via.


Ulteriore edit:

Se guardi questa immagine:
http://upload.wikimedia.org/wikipedia/commons/e/ea/Hasse_diagram_of_powerset_of_3.svg

E' l'esempio (rovesciato, nel senso che noi iniziamo dal basso) del caso in cui ho N=1 e K=|X,Y,Z| = 3

[british]

Mettiamo che io ho un insieme formato da K nodi e devo calcolarmi le combinazioni di nupple di questi K nodi, mi speigo meglio:


Dimmi se ho capito bene, posto che indichiamo con '0' uno spazio vuoto.
Le combinazioni sono con ripetizione? (reimmissione)
Sono veramente combinazioni o disposizioni? (in quest'ultimo caso conta l'ordine)

es.
nodi = { A, B, 0 }, K = |nodi| = 2
N = 2 (coppie)

vogliamo:
A,0
B,0
A,B

o anche (disposizioni):
0,A
0,B
B,A

o anche (con ripetizione):
0,0
A,A
B,B

[guylmaster]

Dimmi se ho capito bene, posto che indichiamo con '0' uno spazio vuoto.
Le combinazioni sono con ripetizione? (reimmissione)
Sono veramente combinazioni o disposizioni? (in quest'ultimo caso conta l'ordine)

es.
nodi = { A, B, 0 }, K = |nodi| = 2
N = 2 (coppie)

vogliamo:
A,0
B,0
A,B

o anche (disposizioni):
0,A
0,B
B,A

o anche (con ripetizione):
0,0
A,A
B,B

Sono SENZA reimmissione e NON conta l'ordine.

Come scritto sopra stiamo valutando l'influenza di un set di variabili {X1,X2,...,Xn} su una variabile Y. Ad esempio come l'insieme di variabili S= {TEMPO, VENTO, TEMPERATURA} influiscano sulla variabile "GIOCO_A_TENNIS", in N differenti epoche. Dire che "GIOCO_A_TENNIS" è influenzata solo da {TEMPO,VENTO} è identico dal dire che è influenzata da {VENTO,TEMPO}. Inoltre non ha senso dire che sia influenzata da {VENTO,TEMPO,VENTO} ovvero le reimmisioni.

E necessario nel diagramma di HASSE inserire una sola variabile "per livello" in totale sugli N insiemi perchè altrimenti si verrebbero a creare nodi identici. Ma visto che tutto questo ci serve per modellare uno spazio di ricerca avere nodi identici significa valutare due volte la stessa soluzione e non ha senso.

Tenete conto quindi che lo scopo è ho N insiemi, ho K variabili, parto dal dire "Al livello 0 nessuna variabile, in ogni insieme, influenza Y (es GIOCO_A_TENNIS) e arrivo alla fine del diagramma con il dire che tutte le variabili, su tutti gli insiemi (sarebbero le epoche) influenzano Y.

Tra l'altro io devo anche modellare gli archi, ovvero tra un nodo ni a livello chesso L, ed un nodo nj a livello L+1 c'è un arco solo se è verificata questa operazione di contenimento:


ni = (S1i,S2i) C nj = (S1j,S2j) solo se S1i C S1j AND S21 C s2j


Ovviamente se vedete il link riguardo il diagramma di hasse avro solo archi da un livello verso quello direttamente successivo, e sono in quel senso.

Per essere ancora più chiari potete vedere questo ulteriore esempio:

https://dl.dropboxusercontent.com/u/8098999/diagramma.png

Qui i abbiamo l'insieme di nodi S={vuoto,X1,X2} ovvero K=3 ed n= 2. Ovviamente il grafico non è del tutto completo, mancano dei rami perchè altrimenti non avrei finito più di disegnarlo.

[Daniels118]

Ho veramente difficoltà a capire il criterio per costruire il livello successivo, ma non mi arrendo :D
L'ultimo grafico che hai postato è molto più esplicativo, ci ragiono un po' su, abbi fiducia ;)

[Daniels118]

Sta diventando sempre più oscuro :muro:
Perchè alcuni nodi hanno un solo padre, altri 2 e altri 3?
Mi spieghi come si costruisce il nodo 12?

[guylmaster]

Prima di tutto creerei una copia dell'insieme dei nodi e vi aggiungerei degli elementi vuoti fino ad avere almeno N elementi, in modo da poter eliminare la singolarità.

Ora, immagina che il risultato del tuo algoritmo sia un insieme di numeri. Ciascuno di questi numeri è la combinazioni di N cifre. Le cifre non sono le classiche da 0 a 9, ma provengono dall'insieme dei nodi. Ora non devi far altro che contare.

Chiamiamo T il numero totale di nodi (inclusi eventuali valori nulli):
T = MAX(K, N)

Chiamiamo V l'insieme dei nodi ed R l'insieme dei risultati.
//Prepara gli indici per selezionare i nodi
Array indici[N];
for i = 0; i < N; i++ {
indici[i] = 0;
}
while (indici[N-1] < K) {
//Crea la tupla prendendo i nodi secondo i valori degli indici
Array tupla[N];
for i = 0; i < N; i++ {
tupla[i] = V[indici[i]];
}
//Inserisce la tupla nei risultati
R.push(tupla);
//Aggiorna gli indici
indici[0]++;
for (i = 0; i < N; i++) {
if (indici[i] == T && i < N - 1) {
indici[i] = 0;
indici[i + 1]++;
} else {
break;
}
}
}
Probabilmente va affinata un po', ma aspetto di sentire cosa ne pensi.

Ho provato ad implementare il tutto in Java per debuggare meglio, ovvero ho creato questa classe:

package utilis;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;

public class ParentsCombinations {

public static void generate(String[] V, int epochs)
{
int K = V.length;
int T = Math.max(K, epochs);
HashSet<String[]> R = new HashSet<String[]>();
ArrayList<String[]> R1 = new ArrayList<String[]>();
//Prepara gli indici per selezionare i nodi
int[] indici= new int[epochs];

for(int i = 0; i < epochs; i++ )
{
indici[i] = 0;
}

while (indici[epochs-1] < K) {
//Crea la tupla prendendo i nodi secondo i valori degli indici
String[] tupla = new String[epochs];
for(int i = 0; i < epochs; i++)
{
tupla[i] = V[indici[i]];
}
//Inserisce la tupla nei risultati
R.add(tupla);
R1.add(tupla);
//Aggiorna gli indici
indici[0]++;
for (int i = 0; i < epochs; i++) {
if (indici[i] == T && i < epochs - 1) {
indici[i] = 0;
indici[i + 1]++;
} else {
break;
}
}
}

/*for(String[] si: R)
{
System.out.print("(");
for(String sj:si)
{
System.out.print("{"+sj + "}, ");
}
System.out.print(")\n");
}*/

for(String[] si: R1)
{
System.out.print("(");
for(String sj:si)
{
System.out.print("{"+sj + "}, ");
}
System.out.print(")\n");
}
//System.out.println(epochs);
}

public static void main(String[] args) throws Exception {

int x= 4;
String[] powerSet = new String[x];
powerSet[0] = "0";
powerSet[1] = "X1";
powerSet[2] = "X2";
powerSet[3] = "X1,X2";

ParentsCombinations.generate(powerSet, 2);
//System.out.println(powerSet.length);
}

}

Guardando gli output e pensandoci bene le possibili combinazioni che deve calcolare le calcola tutte (sebbene rimango i dubbi che ti ho chiesto ieri sul codice tipo perchè T=MAX(N,K)) il problema è che non sono "ordinate" per livello come vorrei io. Io l'ho provato nel caso specifico in cui ho {vuoto,x1,x2} e ho N (che ho chiamato epochs) = 2, dovrei fare qualche altra prova per essere un pò più sicuro che vada in tutti i casi e non sia solo un caso fortuito.

Quindi gli approcci possibili sono:
1) Il più pulito, riuscire ad aggiustarlo in modo che le calcoli nel giusto ordine;
2) Si crea un algoritmo a posteriori che li ordina;

Dove per ordine a me interessa avere prima tutte quelle con 0 variabili sui due insiemi, poi tutte quelle con 1 variabile, ecc ecc. Non mi interessa se viene prima ({X1},{}) o ({},{X2}) mi interessa solo che ad esempio ({X1},{}) che ha una variabile venga prima di ({X1},{X2}) che ne ha 2.

Tra l'altro devo anche capire come "creare" gli archi ovvero valutarne il contenimento. Il problema qui è che questo algoritmo lavorerà anche su numeri di variabili e di epoche molto elevate (già se esce N = 10 con 30 variabili la vedo dura, ma si potrebbe anche lavorare con 100 o più variabili..).

[Daniels118]

T=MAX(N,K)
indica il numero di nodi inclusi gli eventuali vuoti necessari per riuscire a creare delle Nuple.
Per esempio, se vuoi creare delle Nuple di 3 nodi (quindi N=3), ma i nodi di partenza sono solo X1 e X2 (quindi K=2), bisogna considerare l'insieme (X1,X2,vuoto), la cui dimensione è non a caso:
T=MAX(3,2) = 3

Se i nodi fossero stati 5 e N=3, non sarebbe stato necessario aggiungere vuoti, e l'insieme dei nodi sarebbe rimasto di 5 elementi:
T=MAX(3,5) = 5

Devo capire questo:
il tuo output deve essere un sottoinsieme di quello prodotto dal mio algoritmo?
Oppure ti aspetti qualcosa di diverso?

[guylmaster]

Sta diventando sempre più oscuro :muro:
Perchè alcuni nodi hanno un solo padre, altri 2 e altri 3?
Mi spieghi come si costruisce il nodo 12?

I nodi possono avere più padri perchè ho detto non è un normale albero ma è un un diagramma di Hasse:

http://it.wikipedia.org/wiki/Diagramma_di_Hasse

L'idea è che c'è un arco tra due nodi, solo se sono due livelli "vicini", se è soddisfatta l'operazione di contenimento che ti riporto di nuovo essere:

ni = (S1i,S2i) C nj = (S1j,S2j) solo se S1i C S1j AND S21 C s2j

Facciamo l'esempio concreto del nodo 12. Tu a livello 2 (si inizia a contare da 0) hai creato il nodo 6 = ({X1}, {X1}) 7 = ({X1}, {X2}) ed il nodo 8 =({X1,X2}, {}). Da notare che a livello 2 si hanno un totale di 2 variabili.

Ora al livello 3 inizi a creare i nodi con 3 variabili, arrivi al 6 (mettiamo che li fai per ordine di numero) e cosa puoi fare? o aggiungi X2 al primo insieme o aggiungi X2 al secondo insieme, perchè possiamo aggiungere 1 solo nodo per volta e non possiamo avere ripetizioni. Se aggiungiamo X2 al secondo insieme otteniamo proprio il nodo 12 che è = ({X1}{X1,X2}).

Finito di fare le combinazioni del nodo 6 passiamo al nodo 7, se aggiungiamo X1 al secondo insieme del nodo 7 abbiamo di nuovo il 12, ma essendoci già ecco che il 12 ha 2 padri.

8 ora che controllo bene NON E' un padre di 12, mi sono solo super-confuso nel tracciare gli archi, chiedo scusa, 8 non è padre di 12 perchè:

Dati:
8 =({X1,X2}, {}).
12 = ({X1}{X1,X2})

{X1,X2} NON é contenuto in {X1}

Chiedo venia per l'errore :fagiano:

[guylmaster]

T=MAX(N,K)
indica il numero di nodi inclusi gli eventuali vuoti necessari per riuscire a creare delle Nuple.
Per esempio, se vuoi creare delle Nuple di 3 nodi (quindi N=3), ma i nodi di partenza sono solo X1 e X2 (quindi K=2), bisogna considerare l'insieme (X1,X2,vuoto), la cui dimensione è non a caso:
T=MAX(3,2) = 3

Se i nodi fossero stati 5 e N=3, non sarebbe stato necessario aggiungere vuoti, e l'insieme dei nodi sarebbe rimasto di 5 elementi:
T=MAX(3,5) = 5

Devo capire questo:
il tuo output deve essere un sottoinsieme di quello prodotto dal mio algoritmo?
Oppure ti aspetti qualcosa di diverso?


Se funziona in tutti i casi (come spero che sia e potrò dirlo APPENA capisco bene il tuo algoritmo) l'insieme in output è ESATTAMENTE quello a meno dell'ordinamento.

Ovvero dati l'output del tuo algoritmo devo riuscire a dire:
Chi è padre di chi;
A quale livello appartiene ogni nodo (banalmente qui posso contare il numero di nodi).

Non so se creare una specie di "albero" dove ogni nodo ha più padri o metterli in un vettore dove ogni cella contiene i nodi di un livello e poi creare un metodo che mi restituisce tutti i figli.

[guylmaster]

T=MAX(N,K)
indica il numero di nodi inclusi gli eventuali vuoti necessari per riuscire a creare delle Nuple.
Per esempio, se vuoi creare delle Nuple di 3 nodi (quindi N=3), ma i nodi di partenza sono solo X1 e X2 (quindi K=2), bisogna considerare l'insieme (X1,X2,vuoto), la cui dimensione è non a caso:
T=MAX(3,2) = 3

Se i nodi fossero stati 5 e N=3, non sarebbe stato necessario aggiungere vuoti, e l'insieme dei nodi sarebbe rimasto di 5 elementi:
T=MAX(3,5) = 5

Devo capire questo:
il tuo output deve essere un sottoinsieme di quello prodotto dal mio algoritmo?
Oppure ti aspetti qualcosa di diverso?

Questa cosa non mi è chiara, anche se ho 5 nodi e N=3 la combinazione {X1}{X2}{} è valida e va generata!

L'idea del vuoto modella l'evento nell'insieme 3 (epoca 3) per la variabile Y per cui stiamo calcoalndo tutte queste combinazioni, non c'è nessuna variabile X che la influenza. Quindi serve e va calcolato.

Tra l'altro se vedi il mio spezzone di codice in Java l'idea è di mettere anche il vuoto come possibili nodi. Ovviamente non genererai mai la combinazione "vuoto,X".

[wingman87]

Ho provato a scrivere una soluzione banale (direi bruteforce) in pseudocodice. Fammi sapere se ti è chiara:

generator(nodes, k)
result = []
newTuples = [ emptyTuple(k) ] //emptyTuple restituisce una nupla vuota con n=k

while(newTuples is not empty)
nextTuples = []
foreach tuple in newTuples
foreach node in nodes
for(i from 0 to k)
newTuple = insert(tuple, i, node) //insert prova a creare una nuova tupla inserendo node in tuple alla posizione i, restituisce tuple se essa contiene già node alla posizione i
if(newTuple != tuple)
nextTuples.push(newTuple)
result.push(newTuples)
newTuples = nextTuples;
return result

[Daniels118]

Penso di avere finalmente capito tutto, ti aggiorno appena ho novità :D

[wingman87]

Mi sono reso conto che avevo fatto un errore, avevo scritto
newTuple = insert(tuple, k, node)
invece di
newTuple = insert(tuple, i, node)
ho corretto, spero di non aver fatto altri errori...

Pensavo poi che in questo modo generi doppioni però puoi sfruttare questo fatto per la determinazione degli archi perché sai sempre da dove deriva ogni nuova tupla infatti la stessa tupla la ottieni a partire da ogni suo padre.

[guylmaster]

Penso di avere finalmente capito tutto, ti aggiorno appena ho novità :D

Mi spiace di non essere stato troppo chiaro fin dall'inizio :fagiano:

Io sono li che immagino un pò come si potrebbe "adattare" il tuo algoritmo, se hai nuove news fammi sapere :fagiano:

@wingman87: Ora guardo la tua soluzione :)

[guylmaster]

Ho provato a scrivere una soluzione banale (direi bruteforce) in pseudocodice. Fammi sapere se ti è chiara:

generator(nodes, k)
result = []
newTuples = [ emptyTuple(k) ] //emptyTuple restituisce una nupla vuota con n=k

while(newTuples is not empty)
nextTuples = []
foreach tuple in newTuples
foreach node in nodes
for(i from 0 to k)
newTuple = insert(tuple, i, node) //insert prova a creare una nuova tupla inserendo node in tuple alla posizione i, restituisce tuple se essa contiene già node alla posizione i
if(newTuple != tuple)
nextTuples.push(newTuple)
result.push(newTuples)
newTuples = nextTuples;
return result


Sinceramete non mi è chiaro già dall'inizio, all'inizio dici newTuples = [ emptyTuple(k) ] poi fai un ciclo while finchè newTuples non è vuoto, ma quindi manco ci entri mai nel ciclo while?

Comunque la soluzione di Daniels118 sembra esserci molto molto vicino!

[wingman87]

Sinceramete non mi è chiaro già dall'inizio, all'inizio dici newTuples = [ emptyTuple(k) ] poi fai un ciclo while finchè newTuples non è vuoto, ma quindi manco ci entri mai nel ciclo while?

Comunque la soluzione di Daniels118 sembra esserci molto molto vicino!

contiene una tupla vuota, non è vuoto

[Daniels118]

:bsod: Ma almeno vinciamo qualcosa se lo risolviamo? :D

[wingman87]

Scusa, ho scritto di fretta dal cell. Comunque volevo dire che all'inizio del ciclo newTuples non è vuoto ma contiene un elemento: una tupla i cui valori sono tutti insiemi vuoti. Comunque l'algoritmo è semplice. Ad ogni iterazione viene generato un livello dell'albero come ci hai spiegato, a partire dal livello precedente. Al termine di ogni iterazione il livello precedente viene aggiunto alla soluzione mentre il livello generato viene utilizzato per la generazione del successivo. Il livello di partenza contiene solo la tupla composta da insiemi vuoti ed ecco spiegate le prime righe del codice.

[guylmaster]

Scusa, ho scritto di fretta dal cell. Comunque volevo dire che all'inizio del ciclo newTuples non è vuoto ma contiene un elemento: una tupla i cui valori sono tutti insiemi vuoti. Comunque l'algoritmo è semplice. Ad ogni iterazione viene generato un livello dell'albero come ci hai spiegato, a partire dal livello precedente. Al termine di ogni iterazione il livello precedente viene aggiunto alla soluzione mentre il livello generato viene utilizzato per la generazione del successivo. Il livello di partenza contiene solo la tupla composta da insiemi vuoti ed ecco spiegate le prime righe del codice.

Quindi se ho capito bene:

Parto dal livello 0 che ho ({},{})

A questo punto per il livello 1 faccio:

Per ogni epoca (insieme) Ei,
Per ogni possibile variabile Xj
Possibile_soluzione = Inserisco Xj in Ei

Se Possibile_soluzione è una soluzione legale (nessuna replica) e non è già presente tra le possibili soluzioni allora la mantengo, giusto?

Se i livello 2 itero su tutte le soluzioni del livello 1 provando a fare le aggiunte come sopra, quindi in realtà non faccio altro che cambiare "il nodo di partenza" su cui aggiungere un possibile nodo, giusto? Ho capito bene?

[guylmaster]

:bsod: Ma almeno vinciamo qualcosa se lo risolviamo? :D

Purtroppo sono uno studente poverello, se siete di Milano posso offrirvi giusto pizza e birra :fagiano:

Ultime notizie ho "contato" quante combinazioni deve generare l'algoritmo ed ho che:

Con K= 3 ed N= 5 sono 32.768 nodi
Con K= 3 ed N= 6 sono 262144 nodi

Se aumento il k ho che:

Con K= 4 ed N= 5 sono 1.048.576 nodi.

E siamo ancora su numeri giocattolo, se faccio:

Con K= 3 ed N= 7 sono 2.097.152 nodi
Con K= 3 ed N= 8 sono 16.777.216 nodi!

Pensate che devo arrivare "almeno" ad N=10 e K= 10...

[wingman87]

Quindi se ho capito bene:

Parto dal livello 0 che ho ({},{})

A questo punto per il livello 1 faccio:

Per ogni epoca (insieme) Ei,
Per ogni possibile variabile Xj
Possibile_soluzione = Inserisco Xj in Ei

Se Possibile_soluzione è una soluzione legale (nessuna replica) e non è già presente tra le possibili soluzioni allora la mantengo, giusto?

Se i livello 2 itero su tutte le soluzioni del livello 1 provando a fare le aggiunte come sopra, quindi in realtà non faccio altro che cambiare "il nodo di partenza" su cui aggiungere un possibile nodo, giusto? Ho capito bene?
Sì credo che tu abbia capito, anche se usiamo termini diversi :)
Una cosa che mi confonde è il nome "nodo", che abbiamo usato per X1, X2, ecc.., che va in conflitto con il concetto di nodo dell'albero.
Se ho più tempo più tardi o domani provo a spiegarmi ancora meglio, sempre che non arrivi a tradurlo in codice prima... Scusa ma ora devo proprio correre

[guylmaster]

Sì credo che tu abbia capito, anche se usiamo termini diversi :)
Una cosa che mi confonde è il nome "nodo", che abbiamo usato per X1, X2, ecc.., che va in conflitto con il concetto di nodo dell'albero.
Se ho più tempo più tardi o domani provo a spiegarmi ancora meglio, sempre che non arrivi a tradurlo in codice prima... Scusa ma ora devo proprio correre

Si giusto X1 è una variabile. Un nodo è ({},..,{}).

Sto provando a tradurlo in codice ma mi sto perdendo, forse anche grazie all'ora della giornata. Se riesci a darmi qualcosa di meno ad alto livello, ovviamente quando e se avrai tempo, te ne sarei grato.


Intanto l'algoritmo di Daniels118 sono riuscito a farlo funzionare mettendogli una "toppa".
Ovvero:

R diventa un HashMap <numero_di_variabili, lista<tupla>>

Quando creo una nuova tupla mi calcolo il numero di variabili in quella tupla e la inserisco nell'hashmap. Quando ho terminato se uso l'iteratore sull'hashmap mi stampa i risultati in ordine di chiavi e quindi in ordine di livello.

La soluzione però non è elegantissima inoltre per eventuali "migliorie" successive sarebbe meglio se riesco a calcolare le combinazioni 1 livello per volta (ad esempio cosi potrei dire "mi fermo ad un certo livello").

[wingman87]

Purtroppo sono uno studente poverello, se siete di Milano posso offrirvi giusto pizza e birra :fagiano:

Ultime notizie ho "contato" quante combinazioni deve generare l'algoritmo ed ho che:

Con K= 3 ed N= 5 sono 32.768 nodi
Con K= 3 ed N= 6 sono 262144 nodi

Se aumento il k ho che:

Con K= 4 ed N= 5 sono 1.048.576 nodi.

E siamo ancora su numeri giocattolo, se faccio:

Con K= 3 ed N= 7 sono 2.097.152 nodi
Con K= 3 ed N= 8 sono 16.777.216 nodi!

Pensate che devo arrivare "almeno" ad N=10 e K= 10...
Non avevo fatto i conti ma una crescita esponenziale era prevedibile

[Daniels118]

Non ho più la mente fresca come una volta... eppure non pensavo di essere così vecchio!
Proprio a causa della crescita esponenziale sarebbe meglio riuscire a generare direttamente le sole combinazioni valide, ma a dirlo è una cosa e a farlo ne è un'altra... non avrei mai pensato di dirlo, sarà la stanchezza...
Anche se non ho molto tempo a disposizione vi continuo a seguire, se ho la possibilità provo a buttare giù direttamente del codice in java.

[wingman87]

Ho tradotto in Java il mio pseudocodice... mi vergogno un po' perché l'ho scritto un po' da cani, è un sacco che non scrivo codice Java e probabilmente tante cose si potevano fare meglio, però l'algoritmo fa quello che dovrebbe fare... Considera che come ti dicevo non elimina i doppioni.
Ecco il codice:

Tuple.java
import java.util.ArrayList;
import java.util.List;


public class Tuple<T> {

private List<T> values;

public Tuple(int n) {
values = new ArrayList<T>(n);
for(int i=0; i<n; i++)
values.add(null);
}

public void set(int i, T value) {
if(i<0 || i>=values.size())
throw new RuntimeException();
values.set(i, value);
}

public T get(int i) {
if(i<0 || i>=values.size())
throw new RuntimeException();
return values.get(i);
}

public int size(){
return values.size();
}

}


Main.java
import java.util.*;


public class Main {

public static void main(String[] args) {
List<Tuple<Set<String>>> tuples = generator(Arrays.asList("X1", "X2"), 3);

for(Tuple<Set<String>> tuple : tuples)
System.out.println(tupleToString(tuple));
}

public static List<Tuple<Set<String>>> generator(List<String> vars, int k) {
List<Tuple<Set<String>>> ret = new LinkedList<Tuple<Set<String>>>();

List<Tuple<Set<String>>> newTuples = new LinkedList<Tuple<Set<String>>>();
newTuples.add(emptyTuple(k));

while(!newTuples.isEmpty())
{
List<Tuple<Set<String>>> nextTuples = new LinkedList<Tuple<Set<String>>>();
for(Tuple<Set<String>> tuple : newTuples) {
for(String var : vars) {
for(int i = 0; i < k; i++) {
Tuple<Set<String>> newTuple = insert(tuple, i, var);
if(newTuple != tuple)
nextTuples.add(newTuple);
}
}
}
ret.addAll(newTuples);
newTuples = nextTuples;
}

return ret;
}

private static Tuple<Set<String>> insert(Tuple<Set<String>> tuple, int i, String var) {
if(tuple.get(i).contains(var))
return tuple;
Tuple<Set<String>> newTuple = new Tuple<Set<String>>(tuple.size());

for(int j = 0; j < tuple.size(); j++)
newTuple.set(j, (Set<String>)((TreeSet<String>)tuple.get(j)).clone());
newTuple.get(i).add(var);

return newTuple;
}

public static Tuple<Set<String>> emptyTuple(int k) {
Tuple<Set<String>> ret = new Tuple<Set<String>>(k);
for(int i=0; i<k; i++)
ret.set(i, new TreeSet<String>());
return ret;
}

public static String tupleToString(Tuple<Set<String>> tuple) {
String ret = "(";
for(int i= 0; i < tuple.size(); i++) {
if(i != 0)
ret += ",";
ret += "{";

boolean first = true;
for(String var : tuple.get(i)) {
if(!first)
ret += ",";
first = false;
ret += var;
}

ret += "}";
}
ret += ")";
return ret;
}
}



Questo è l'output con l'input che ho fornito ([X1,X2], 3)
Sono 1957 tuple... l'ho cancellato...

[wingman87]

Per curiosità volevo sapere il numero di tuple effettive, ho modificato il main così:
public static void main(String[] args) {
List<Tuple<Set<String>>> tuples = generator(Arrays.asList("X1", "X2"), 3);

//for(Tuple<Set<String>> tuple : tuples)
//System.out.println(tupleToString(tuple));
System.out.println(tuples.size());

HashSet<Tuple<Set<String>>> tuplesSet = new HashSet<Tuple<Set<String>>>();
tuplesSet.addAll(tuples);
System.out.println(tuplesSet.size());
}
e aggiunto questi metodi a Tuple

@Override
public boolean equals(Object obj) {
if(obj == null)
return false;

if(!(obj instanceof Tuple<?>))
return false;

Tuple<?> tuple = (Tuple<?>)obj;

if(this.size() != tuple.size())
return false;

for(int i=0; i<this.size(); i++)
if(!values.get(i).equals(tuple.get(i)))
return false;
return true;
}

@Override
public int hashCode() {
int ret = 0;
for(int i=0; i<this.size(); i++)
if(values.get(i) != null)
ret += values.get(i).hashCode();
return ret;
}


Comunque non usare assolutamente questo codice così com'è, diciamo che è solo un Proof Of Concept, bisogna dargli una bella sistemata :)

Ah e le tuple effettive erano 64, contro le 1957 generate

[wingman87]

Facendo un po' di test sembra che il numero di tuple generate sia 2^(n*k), con n la grandezza della tupla e k il numero di variabili. Con questa formula mi ritrovo anche con i calcoli che avevi postato.

Quindi il numero di tuple per n=10 e k=10 è
1267650600228229401496703205376
Auguri a generarle tutte :D

[guylmaster]

Facendo un po' di test sembra che il numero di tuple generate sia 2^(n*k), con n la grandezza della tupla e k il numero di variabili. Con questa formula mi ritrovo anche con i calcoli che avevi postato.

Quindi il numero di tuple per n=10 e k=10 è
1267650600228229401496703205376
Auguri a generarle tutte :D

In realtà è (2^k)^n quindi non è esponenziale ma super-esponenziale.

Infatti (2^4)^5 fa proprio 1.048.576

Mentre (2^3)^5 fa proprio 32.768

Tutto il sistema girerà tramite ambiente Hadoop (mediante paradigma map reduce), ovvero un sistema che permette di paralelizzare su più macchine. Se riuscissi ad organizzare il calcolo in modo che si possa eseguire in paralello avrei qualche speranza :fagiano:

[guylmaster]

Non ho più la mente fresca come una volta... eppure non pensavo di essere così vecchio!
Proprio a causa della crescita esponenziale sarebbe meglio riuscire a generare direttamente le sole combinazioni valide, ma a dirlo è una cosa e a farlo ne è un'altra... non avrei mai pensato di dirlo, sarà la stanchezza...
Anche se non ho molto tempo a disposizione vi continuo a seguire, se ho la possibilità provo a buttare giù direttamente del codice in java.

Il tuo codice infatti genera tutte e sole quelle necessarie, il problema è che c'è poi bisogno di un riordinamento a posteriori che appunto su una crescita esponenziale non è il massimo. Se si riuscisse a fare in modo che le calcoli in maniera già ordinata sarebbe già un buon risultato. Poi mi dovrò scervellare nel capire se c'è un modo per parallelizzare il tutto.

[guylmaster]

Per curiosità volevo sapere il numero di tuple effettive, ho modificato il main così:
public static void main(String[] args) {
List<Tuple<Set<String>>> tuples = generator(Arrays.asList("X1", "X2"), 3);

//for(Tuple<Set<String>> tuple : tuples)
//System.out.println(tupleToString(tuple));
System.out.println(tuples.size());

HashSet<Tuple<Set<String>>> tuplesSet = new HashSet<Tuple<Set<String>>>();
tuplesSet.addAll(tuples);
System.out.println(tuplesSet.size());
}
e aggiunto questi metodi a Tuple

@Override
public boolean equals(Object obj) {
if(obj == null)
return false;

if(!(obj instanceof Tuple<?>))
return false;

Tuple<?> tuple = (Tuple<?>)obj;

if(this.size() != tuple.size())
return false;

for(int i=0; i<this.size(); i++)
if(!values.get(i).equals(tuple.get(i)))
return false;
return true;
}

@Override
public int hashCode() {
int ret = 0;
for(int i=0; i<this.size(); i++)
if(values.get(i) != null)
ret += values.get(i).hashCode();
return ret;
}


Comunque non usare assolutamente questo codice così com'è, diciamo che è solo un Proof Of Concept, bisogna dargli una bella sistemata :)

Ah e le tuple effettive erano 64, contro le 1957 generate


Ovviamente prima di metterlo "in uso" qualsiasi codice che scegliero dovrò farlo mio e probabilmente dovrò adattarlo per renderlo "paralello".

Ad ogni modo con questi operatori che hai aggiunto il risultato è buono. In tempi di computazione è sicuramente molto meglio di calcolarli disordinati come facevo prima e ordinarli dopo.

Un altra cosa ulteriore che servirà, ma credo sarà facile da implementare, è l'operatore di contenimento, mi serve perchè io quando si verificano determinate condizioni devo poter "potare" tutti i superset di un determinato insieme, ovvero la solita operazione ma propagata sui figli, figli di figli, figli di figli di figli, eccetera:

ni = (S1i,S2i) C nj = (S1j,S2j) solo se S1i C S1j AND S21 C s2j

Ovvero se si verificano determiante regole tutti i nodi (a scendere) collegati da un arco a partire da un determinato nodo, devono poter essere cancellati.

Il problmea non sarà tanto "farlo" ma farlo in maniera efficente :fagiano:

Comunque inanzi tutto un grazie mille a tutti e due per l'estremo aiuto che mi state dando!

Edit: Probabilmente avrete già visualizzato bene il problema, ma in caso vi potesse essere d'aiuto questo è un diagramma di Hasse completo su 2 nodi e 2 insiemi:
https://dl.dropboxusercontent.com/u/8098999/hasse.png


Edit: @wingman87 sebbene ho capito il funzionamento in generale posso chiederti di aggiungere qualche commento nel tuo codice per capirlo meglio? Ad esempio se io ho K=10 ed N=10, posso dire in qualche modo "ok inizia a generare le combinaioni su 10 insiemi e su 10 nodi, ma fermati al livello chessò 100"? e se si che modifiche dovrei fare nel tuo codice ?

[guylmaster]

Ultimi aggiornamenti:

Sull'algoritmo di wingman87 riesco perfettamente a dirgli di fermarsi ad un determianto livello. Questo è una cosa buona, molto buona, perchè potrei adottare come criterio di "fermarsi ad un determinato livello".

Inoltre mi sono messo a mettere un pò di commenti qua è la per essere sicuro di aver capito tutto. A seguire il codice aggiornato :fagiano:

Il problema è che mi sono accorto che è più lento dell'algoritmo di Daniels118, con tutto che nel suo algoritmo prima le genero disordinate e poi (Tramite mia modifica) le ordino a posteriori. Probabilmente il fatto di generare comunque combinazioni ripetute per poi semplicemente non inserirle rallenta tutto di molto. Se si riuscisse a tirar su un algoritmo che le genera in maniera ordinata e non genera doppioni sarebbe il massimo.


import java.util.*;


//Questa è un nodo del nostro diagramma di Hasse (quindi parentset su N epoche)
class Tuple<T> {

private List<T> values;

public Tuple(int n) {
values = new ArrayList<T>(n);
for(int i=0; i<n; i++)
values.add(null);
}

public void set(int i, T value) {
if(i<0 || i>=values.size())
throw new RuntimeException();
values.set(i, value);
}

public T get(int i) {
if(i<0 || i>=values.size())
throw new RuntimeException();
return values.get(i);
}

public int size(){
return values.size();


}

public boolean equals(Object obj) {
if(obj == null)
return false;

if(!(obj instanceof Tuple<?>))
return false;

Tuple<?> tuple = (Tuple<?>)obj;

if(this.size() != tuple.size())
return false;

for(int i=0; i<this.size(); i++)
if(!values.get(i).equals(tuple.get(i)))
return false;
return true;
}

@Override
public int hashCode() {
int ret = 0;
for(int i=0; i<this.size(); i++)
if(values.get(i) != null)
ret += values.get(i).hashCode();
return ret;
}


}

public class HasseDiagram {

public static void main(String[] args) {

List<Tuple<Set<String>>> tuples = generator(Arrays.asList("X1", "X2", "X3"), 5);

for(Tuple<Set<String>> tuple : tuples)
System.out.println(tupleToString(tuple));
System.out.println(tuples.size());

HashSet<Tuple<Set<String>>> tuplesSet = new HashSet<Tuple<Set<String>>>();
tuplesSet.addAll(tuples);
System.out.println(tuplesSet.size());
}

public static List<Tuple<Set<String>>> generator(List<String> vars, int epochs, int maxLivelli) {

//Questi sono tutti i nodi che ritorniamo su tutti i livelli
List<Tuple<Set<String>>> ret = new ArrayList<Tuple<Set<String>>>();

//Queste sono i nodi di un intero livello
HashSet<Tuple<Set<String>>> newTuples = new HashSet<Tuple<Set<String>>>();

//All'inizio aggiungiamo SOLO il nodo vuoto ({},..,{})
newTuples.add(emptyTuple(epochs));

int livello = 0;
//finchè c'è un nodo da espandere
while(!newTuples.isEmpty() && livello <= maxLivelli)
{
System.out.println(livello);
livello++;
//tuple di un intero livello, all'inizio vuoto
HashSet<Tuple<Set<String>>> nextTuples = new HashSet<Tuple<Set<String>>>();

//Genero le tuple di un intero livello
//per ogni tupla del livello da espandere
for(Tuple<Set<String>> tuple : newTuples) {
//per ogni possibile variabile con cui la possiamo espandere
for(String var : vars) {
//per ogni possibile epoca
for(int i = 0; i < epochs; i++)
{
//creo una nuova tupla prendendo la tupla che stiamo considerando e provando ad espanderla con una variabile nell'i-esima epoca
Tuple<Set<String>> newTuple = insert(tuple, i, var);

//Aggiungo il nuovo nodo a quelli da espandere nel prossimo livello
if(newTuple != tuple)
{
nextTuples.add(newTuple);
}
}
}
}

//aggiungo tutte le tuple del livello PRECEDENTE all'insieme di ritorno
ret.addAll(newTuples);

//prendo le tuple create al livello attuale per espanderle
newTuples = nextTuples;
}

return ret;
}

public static List<Tuple<Set<String>>> generator(List<String> vars, int epochs) {

//Questi sono tutti i nodi che ritorniamo su tutti i livelli
List<Tuple<Set<String>>> ret = new ArrayList<Tuple<Set<String>>>();

//Queste sono i nodi di un intero livello
HashSet<Tuple<Set<String>>> newTuples = new HashSet<Tuple<Set<String>>>();

//All'inizio aggiungiamo SOLO il nodo vuoto ({},..,{})
newTuples.add(emptyTuple(epochs));

//finchè c'è un nodo da espandere
while(!newTuples.isEmpty())
{
//tuple di un intero livello, all'inizio vuoto
HashSet<Tuple<Set<String>>> nextTuples = new HashSet<Tuple<Set<String>>>();

//Genero le tuple di un intero livello
//per ogni tupla del livello da espandere
for(Tuple<Set<String>> tuple : newTuples) {
//per ogni possibile variabile con cui la possiamo espandere
for(String var : vars) {
//per ogni possibile epoca
for(int i = 0; i < epochs; i++)
{
//creo una nuova tupla prendendo la tupla che stiamo considerando e provando ad espanderla con una variabile nell'i-esima epoca
Tuple<Set<String>> newTuple = insert(tuple, i, var);

//Aggiungo il nuovo nodo a quelli da espandere nel prossimo livello
if(newTuple != tuple)
{
nextTuples.add(newTuple);
}
}
}
}

//aggiungo tutte le tuple del livello PRECEDENTE all'insieme di ritorno
ret.addAll(newTuples);

//prendo le tuple create al livello attuale per espanderle
newTuples = nextTuples;
}

return ret;
}

private static Tuple<Set<String>> insert(Tuple<Set<String>> tuple, int i, String var) {
if(tuple.get(i).contains(var))
return tuple;
Tuple<Set<String>> newTuple = new Tuple<Set<String>>(tuple.size());

for(int j = 0; j < tuple.size(); j++)
newTuple.set(j, (Set<String>)((TreeSet<String>)tuple.get(j)).clone());
newTuple.get(i).add(var);

return newTuple;
}

public static Tuple<Set<String>> emptyTuple(int k) {
Tuple<Set<String>> ret = new Tuple<Set<String>>(k);
for(int i=0; i<k; i++)
ret.set(i, new TreeSet<String>());
return ret;
}

public static String tupleToString(Tuple<Set<String>> tuple) {
String ret = "(";
for(int i= 0; i < tuple.size(); i++) {
if(i != 0)
ret += ",";
ret += "{";

boolean first = true;
for(String var : tuple.get(i)) {
if(!first)
ret += ",";
first = false;
ret += var;
}

ret += "}";
}
ret += ")";
return ret;
}
}

Ancora un grazie per la pazienza e l'aiuto!


Edit: Mi sono accorto che al livello 1 ogni nodo ha un genitore, al livello 2 ogni nodo ne hanno 2 e via discorrendo. Questo vuol dire che se prendiamo ogni nodo e lo proviamo ad espandere "singolarmente" livello per livello come facciamo nell'algoritmo di wingman87 abbiamo che al primo livello generiamo 2 volte ogni nodo del secondo livello. Al terzo livello li generiamo 3 volte e via discorrendo. E' vero che mettendo tutto in un insieme non is hanno doppioni (o triploni ecc) ma comunque li generiamo.

[wingman87]

Il problema del mio algoritmo è che considera tutti gli archi del grafo di Hasse. Questo però come ti dicevo può anche essere un vantaggio se ti serve relazionare tra loro i nodi e ti conviene farlo nel momento in cui vengono generati. Invece nell'algoritmo di Daniels vengono considerati tutti i nodi ma non gli archi (che sono mooooolti di più dei nodi) che va benissimo però se hai bisogno anche di relazionare tra loro i nodi sarà necessario un ulteriore lavoro a posteriori.
Ciò non esclude che possa esistere una via di mezzo che coniuga entrambi i pregi che per riassumere sono: nel primo algoritmo hai le relazioni tra i nodi ma un tempo molto maggiore, nel secondo hai un tempo molto inferiore ma non hai le relazioni tra i nodi.
L'ideale sarebbe trovare solo i nodi ed avere un modo semplice di capire quali sono gli archi. Chessò, ad esempio è possibile che secondo un certo ordinamento i nodi padre di un nodo di indice i siano tutti quelli i cui indici fanno parte di una successione che è funzione di i.
Oppure ancora meglio di trovare tutti i nodi, sarebbe bello trovare una relazione semplice tra l'indice di un nodo ed esso stesso. Per intenderci, ad esempio, tu potresti dire alla funzione che esprime la relazione indice-nodo: dammi il nodo di indice i per questi valori k e n, e la funzione ti restituisce la tupla. La relazione deve però essere abbastanza semplice, altrimenti non ne vale la pena :)

Comunque mi sembra un approccio intrattabile vista la crescita del numero di nodi, mi chiedo a cosa ti possa servire tutto questo... probabilmente c'è un modo migliore per risolvere il problema da cui sei partito.

[guylmaster]

Il problema del mio algoritmo è che considera tutti gli archi del grafo di Hasse. Questo però come ti dicevo può anche essere un vantaggio se ti serve relazionare tra loro i nodi e ti conviene farlo nel momento in cui vengono generati. Invece nell'algoritmo di Daniels vengono considerati tutti i nodi ma non gli archi (che sono mooooolti di più dei nodi) che va benissimo però se hai bisogno anche di relazionare tra loro i nodi sarà necessario un ulteriore lavoro a posteriori.
Ciò non esclude che possa esistere una via di mezzo che coniuga entrambi i pregi che per riassumere sono: nel primo algoritmo hai le relazioni tra i nodi ma un tempo molto maggiore, nel secondo hai un tempo molto inferiore ma non hai le relazioni tra i nodi.
L'ideale sarebbe trovare solo i nodi ed avere un modo semplice di capire quali sono gli archi. Chessò, ad esempio è possibile che secondo un certo ordinamento i nodi padre di un nodo di indice i siano tutti quelli i cui indici fanno parte di una successione che è funzione di i.
Oppure ancora meglio di trovare tutti i nodi, sarebbe bello trovare una relazione semplice tra l'indice di un nodo ed esso stesso. Per intenderci, ad esempio, tu potresti dire alla funzione che esprime la relazione indice-nodo: dammi il nodo di indice i per questi valori k e n, e la funzione ti restituisce la tupla. La relazione deve però essere abbastanza semplice, altrimenti non ne vale la pena :)

Comunque mi sembra un approccio intrattabile vista la crescita del numero di nodi, mi chiedo a cosa ti possa servire tutto questo... probabilmente c'è un modo migliore per risolvere il problema da cui sei partito.

Su un altro forum mi avevano consigliato un algoritmo che di per se non era granchè efficente ma che consigliava un modo per "tirare fuori gli archi" molto interessante.

L'idea era di associare un numero primo ad ogni variabile, ad esempio:

Vuoto = 1
X1 = 2
X2 = 3

Ora se prendo un nodo del tipo n1 = ({X1},{}) e n2= ({X1},{X1,X2}) dico che {X1} = 2 {}=1 e {X1,X2} è = 2*3=6.

Bene se faccio {X1} % {X1} il resto è 0 quindi è contenuto. Se faccio {X1,X2} % {} il resto è sempre zero quindi è contenuto. Se entrambi gli insiemi sono contenuti allora c'è un arco!

Se invece avessi avuto:
n1 = ({X2},{})
n2= ({X1},{X1,X2})

Avrei avuto per il primo insieme della coppia 2 % 3 che non è zero.

Gli archi potrebbero infatti servirmi in fase di pruning Perchè io devo poter dire ad un livello chesso 4 del diagramma di hasse che tutti i superset (ovvero i discendenti) di un determinato nodo vanno tagliati.

Edit: E' il problema ad essere di per se esponenziale. Probabilmente una volta fatto l'algoritmo adoterrò delle tecniche di pruning tipo "non calcolarmi tutto il diagramma ma fermarmi al livello k-esimo", oltre che eliminare determinate possibilità.

Comunque grazie mille ancora per l'aiuto.