[Algoritmo Java] combinazioni di coppie

guylmaster · 27-02-2014, 14:33

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 · 27-02-2014, 15:52

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.

Codice:

//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 · 27-02-2014, 16:13

Quote:

Originariamente inviato da 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.

Codice:

//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 · 27-02-2014, 17:22

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

Se io ho:

Codice:

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

Codice:

indici = [0,0,0]
tupla = [vuoto,vuto,vuoto]
aggiorono indici = [1,0,0]

Al secondo passo ho

Codice:

indici = [1,0,0]
tupla = [X1,vuto,vuoto]
aggiorono indici = [2,0,0]

Al terzo passo ho

Codice:

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

Codice:

indici = [0,1,0]
tupla = [vuoto,X1,vuoto]
aggiorono indici = [1,1,0]

Al quinto passo c'è qualcosa che non va perchè ho:

Codice:

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)

Codice:

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

Daniels118 · 27-02-2014, 21:01

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 · 27-02-2014, 22:56

Quote:

Originariamente inviato da 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?

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:

Codice:

({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:

Codice:

 ({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è

Codice:

{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:

Codice:

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/wikipedi...erset_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 · 28-02-2014, 01:16

Quote:

Originariamente inviato da guylmaster

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 · 28-02-2014, 09:17

Quote:

Originariamente inviato da british

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:

Codice:

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/.../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 · 28-02-2014, 09:23

Ho veramente difficoltà a capire il criterio per costruire il livello successivo, ma non mi arrendo

L'ultimo grafico che hai postato è molto più esplicativo, ci ragiono un po' su, abbi fiducia

Daniels118 · 28-02-2014, 09:56

Sta diventando sempre più oscuro

Perchè alcuni nodi hanno un solo padre, altri 2 e altri 3?
Mi spieghi come si costruisce il nodo 12?

guylmaster · 28-02-2014, 10:20

Quote:

Originariamente inviato da 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.

Codice:

//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:

Codice:

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 · 28-02-2014, 10:31

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 · 28-02-2014, 10:32

Quote:

Originariamente inviato da Daniels118

Sta diventando sempre più oscuro

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:

Codice:

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

guylmaster · 28-02-2014, 10:35

Quote:

Originariamente inviato da 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?

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 · 28-02-2014, 10:39

Quote:

Originariamente inviato da 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?

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 · 28-02-2014, 11:14

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

Codice:

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 · 28-02-2014, 12:06

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

wingman87 · 28-02-2014, 12:49

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 · 28-02-2014, 14:16

Quote:

Originariamente inviato da Daniels118

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

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

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

@wingman87: Ora guardo la tua soluzione

guylmaster · 28-02-2014, 14:19

Quote:

Originariamente inviato da wingman87

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

Codice:

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!

27-02-2014, 14:33	#1
guylmaster Senior Member Iscritto dal: Aug 2002 Messaggi: 2518	[Algoritmo Java] combinazioni di coppie 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.

27-02-2014, 15:52	#2
Daniels118 Senior Member Iscritto dal: Jan 2014 Messaggi: 852	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. Codice: //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.

27-02-2014, 17:22	#4
guylmaster Senior Member Iscritto dal: Aug 2002 Messaggi: 2518	Sto provando a fare dei trace per capire meglio, inanzi tutto la storia delle singolarità non l'ho capita. Se io ho: Codice: 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 Codice: indici = [0,0,0] tupla = [vuoto,vuto,vuoto] aggiorono indici = [1,0,0] Al secondo passo ho Codice: indici = [1,0,0] tupla = [X1,vuto,vuoto] aggiorono indici = [2,0,0] Al terzo passo ho Codice: 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 Codice: indici = [0,1,0] tupla = [vuoto,X1,vuoto] aggiorono indici = [1,1,0] Al quinto passo c'è qualcosa che non va perchè ho: Codice: 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) Codice: level0: ({}, {}) level1: ({1}, {}); ({2}, {}); ({}, {1}); ({}, {2}) level2: ({1,2}, {}); ({1}, {1}); ({1}, {2}); ({2}, {1}); ({2}, {2}); ({}, {1,2}); [..] Ultima modifica di guylmaster : 27-02-2014 alle 17:41.

27-02-2014, 21:01	#5
Daniels118 Senior Member Iscritto dal: Jan 2014 Messaggi: 852	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?

28-02-2014, 09:23	#9
Daniels118 Senior Member Iscritto dal: Jan 2014 Messaggi: 852	Ho veramente difficoltà a capire il criterio per costruire il livello successivo, ma non mi arrendo L'ultimo grafico che hai postato è molto più esplicativo, ci ragiono un po' su, abbi fiducia

28-02-2014, 09:56	#10
Daniels118 Senior Member Iscritto dal: Jan 2014 Messaggi: 852	Sta diventando sempre più oscuro Perchè alcuni nodi hanno un solo padre, altri 2 e altri 3? Mi spieghi come si costruisce il nodo 12?

28-02-2014, 10:31	#12
Daniels118 Senior Member Iscritto dal: Jan 2014 Messaggi: 852	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?

28-02-2014, 12:06	#17
Daniels118 Senior Member Iscritto dal: Jan 2014 Messaggi: 852	Penso di avere finalmente capito tutto, ti aggiorno appena ho novità

28-02-2014, 12:49	#18
wingman87 Senior Member Iscritto dal: Nov 2005 Messaggi: 2774	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.

Strumenti
Mostra una versione stampabile Invia questa pagina per email