[JAVA] Numeri veramente random

[VegetaSSJ5]

Ragazzi per un progetto devo fare un generatore di istanze per un problema di ottimizzazione, che deve essere realizzato in java. Grosso modo è pronto... Ma se lavora così mi conviene generare queste istanze con la fantasia piuttosto che con questo generatore...

Praticamente mi genera un universo U di n items ed m sottinsiemi disgiunti che devono coprire tutti gli n oggetti. Ovviamente, essendo disgiunti, il numero di sottinsiemi è m t.c. 0 < m <= n

Tanto per fare un esempio mi genera un universo di 2300 items e 1900 sottinsiemi. Ora viene il bello, anzi il brutto....

Prendo il primo sottinsieme e genero randomicamente la cardinalità: 170... bene, andiamo avanti, secondo sottinsieme: cardinalità 1. terzo: 1, poi 1, 1 e così via e ogni tanto ne genera qualcuno più grosso (altrimenti non coprirebbe tutti gli oggetti)....

Ragazzi posso anche capire che mi generi un'istanza fatta in questo modo.... Ma non è possibile che in diverse decine di esecuzioni mi generi le cardinalità dei sottinsiemi tutte fatte in questo modo...

Potete cortesemente darmi una mano a capire dove sbaglio?

Grazie!

[pernacentus]

Come inizializzi l'oggetto random? Se utilizzi il costruttore new Random(long seed) mettendo sempre lo stesso seed è ovvio che ad ogni esecuzione le istanze dei sottoinsiemi abbiano sempre le stesse cardinalità. Poi se vuoi una distribuzione più casuale possibile non utilizzare Random, ma SecureRandom.

[VegetaSSJ5]

Originariamente inviato da pernacentus

Come inizializzi l'oggetto random? Se utilizzi il costruttore new Random(long seed) mettendo sempre lo stesso seed è ovvio che ad ogni esecuzione le istanze dei sottoinsiemi abbiano sempre le stesse cardinalità. Poi se vuoi una distribuzione più casuale possibile non utilizzare Random, ma SecureRandom.

ah.....
quindi Random va inizializzato con un parametro long?
chiedo scusa ma in effetti non ho molta esperienza con il java. Semplicemente mi creo l'oggetto

Random oRandGenoRandGen = new Random();

e da lì comincio con la generazione di numeri casuali (che ripeto sono dell'ordine delle migliaia) in questo modo


oRandGen.nextInt(iNumMax);
ecc...

Come mi consigli di correggere?
Inoltre cos'è SecureRandom?
Grazie....

[wingman87]

Originariamente inviato da VegetaSSJ5

Ragazzi per un progetto devo fare un generatore di istanze per un problema di ottimizzazione, che deve essere realizzato in java. Grosso modo è pronto... Ma se lavora così mi conviene generare queste istanze con la fantasia piuttosto che con questo generatore...

Praticamente mi genera un universo U di n items ed m sottinsiemi disgiunti che devono coprire tutti gli n oggetti. Ovviamente, essendo disgiunti, il numero di sottinsiemi è m t.c. 0 < m <= n

Tanto per fare un esempio mi genera un universo di 2300 items e 1900 sottinsiemi. Ora viene il bello, anzi il brutto....

Prendo il primo sottinsieme e genero randomicamente la cardinalità: 170... bene, andiamo avanti, secondo sottinsieme: cardinalità 1. terzo: 1, poi 1, 1 e così via e ogni tanto ne genera qualcuno più grosso (altrimenti non coprirebbe tutti gli oggetti)....

Ragazzi posso anche capire che mi generi un'istanza fatta in questo modo.... Ma non è possibile che in diverse decine di esecuzioni mi generi le cardinalità dei sottinsiemi tutte fatte in questo modo...

Potete cortesemente darmi una mano a capire dove sbaglio?

Grazie!

Stavo pensando che comunque è inevitabile con 1900 sottoinsiemi ed un universo di 2300 oggetti avere almeno 1500 sottoinsiemi da un elemento solo.
Una cosa che potresti fare è mettere in tutti i 1900 sottoinsiemi un solo elemento e poi mettere i 400 rimanenti qua e là a caso. In questo modo però molto difficilmente andrai oltre i 5 elementi nello stesso sottoinsieme (ho sparato una cifra a caso).
Comunque il costruttore di Random senza parametri inizializza da solo il seed in modo che molto difficilmente tra un'esecuzione e l'altra la sequenza di numeri generati si ripeta.

[VegetaSSJ5]

Originariamente inviato da wingman87

Stavo pensando che comunque è inevitabile con 1900 sottoinsiemi ed un universo di 2300 oggetti avere almeno 1500 sottoinsiemi da un elemento solo.
Una cosa che potresti fare è mettere in tutti i 1900 sottoinsiemi un solo elemento e poi mettere i 400 rimanenti qua e là a caso. In questo modo però molto difficilmente andrai oltre i 5 elementi nello stesso sottoinsieme (ho sparato una cifra a caso).
Comunque il costruttore di Random senza parametri inizializza da solo il seed in modo che molto difficilmente tra un'esecuzione e l'altra la sequenza di numeri generati si ripeta.

ciò che dici è vero....
però mi succede anche che mi genera un universo di 2000 oggetti e 20 sottoinsiemi di cui i primi contengono parecchi elementi (300/400) e gli altri un solo elemento.... vorrei evitare questa sfilza di 1....
so che dopo un certo numero di insiemi grandi, inevitabilmente si scende con la cardinalità, però non vorrei che succeda dopo 2/3 insiemi....

quindi per l'inizializzazione del Random va bene come ho fatto io suppongo...

[wingman87]

Originariamente inviato da VegetaSSJ5

ciò che dici è vero....
però mi succede anche che mi genera un universo di 2000 oggetti e 20 sottoinsiemi di cui i primi contengono parecchi elementi (300/400) e gli altri un solo elemento.... vorrei evitare questa sfilza di 1....
so che dopo un certo numero di insiemi grandi, inevitabilmente si scende con la cardinalità, però non vorrei che succeda dopo 2/3 insiemi....

quindi per l'inizializzazione del Random va bene come ho fatto io suppongo...

Potresti provare lo stesso approccio che dicevo nello scorso post, sperando che non vengano delle cardinalità troppo uniformamente distribuite (20 sottoinsiemi da 100 elementi ciascuno).
Io proverei, se poi mi viene qualche altra idea ti faccio sapere.

EDIT: sì il Random va bene. Comunque se vuoi dare un'occhiata anche a SecureRandom, vedi qua: LINK

[pernacentus]

Se tu provassi con:

int[] sottoinsiemi = new int[numSottoinsiemi];
for(int i=0;i<numSottoinsiemi;i++){
			sottoinsiemi[i] = r.nextInt(noggetti) + 1;
}

Solo che non ho capito se la somma delle cardinalità dei sottoinsiemi deve essere uguale al numero di oggetti, oppure se il problema di ottimizzazione è proprio il Partition Problem e devi stabilire se gli oggetti possono essere contenuti in un insieme composto dai vari sottoinsiemi disgiunti.

[VegetaSSJ5]

Originariamente inviato da pernacentus

Se tu provassi con:

int[] sottoinsiemi = new int[numSottoinsiemi];
for(int i=0;i<numSottoinsiemi;i++){
			sottoinsiemi[i] = r.nextInt(noggetti) + 1;
}

Solo che non ho capito se la somma delle cardinalità dei sottoinsiemi deve essere uguale al numero di oggetti, oppure se il problema di ottimizzazione è proprio il Partition Problem e devi stabilire se gli oggetti possono essere contenuti in un insieme composto dai vari sottoinsiemi disgiunti.

la somma delle cardinalità dei sottoinsiemi deve essere pari al numero totale di oggetti. si tratta del multiple choice knapsack. allego il pezzo di codice che genera i sottoinsiemi e vi associa gli oggetti (per comodità ho eliminato le istruzioni che scrivono su file):

for (i = 1; i <= iNumSubsets; i++) {
	// DETERMINA LA MASSIMA CARDINALITA' DEL SOTTOINSIEME CHE E' PARI AL
	// NUMERO DI OGGETTO RIMANENTI MENO IL NUMERO DI SOTTOINSIEMI DA INSERIRE
	// SE STO INSERENDO L'ULTIMO SOTTOINSIEME VI INSERISCO TUTTI GLI OGGETTI RIMANENTI
	if (i < iNumSubsets) iCardSubset = 1 + oRandGen.nextInt(oItemList.size() - (iNumSubsets - i));
	else iCardSubset = oItemList.size();

	// GENERO I NUMERI DA INSERIRE NEL SOTTINSIEME
	for (j = 1; j <= iCardSubset; j++) {
		// PRENDO L'INDICE DI UN ELEMENTO A CASO E SCRIVO NEL FILE L'ELEMENTO CORRISPONDENTE A QUELL'INDICE
		iItemIndex = oRandGen.nextInt(oItemList.size());
		// RIMUOVO L'ELEMENTO DALLA LISTA
		oItemList.remove(iItemIndex);
	}
}

[pernacentus]

Originariamente inviato da VegetaSSJ5

la somma delle cardinalità dei sottoinsiemi deve essere pari al numero totale di oggetti. si tratta del multiple choice knapsack. allego il pezzo di codice che genera i sottoinsiemi e vi associa gli oggetti (per comodità ho eliminato le istruzioni che scrivono su file):

for (i = 1; i <= iNumSubsets; i++) {
	// DETERMINA LA MASSIMA CARDINALITA' DEL SOTTOINSIEME CHE E' PARI AL
	// NUMERO DI OGGETTO RIMANENTI MENO IL NUMERO DI SOTTOINSIEMI DA INSERIRE
	// SE STO INSERENDO L'ULTIMO SOTTOINSIEME VI INSERISCO TUTTI GLI OGGETTI RIMANENTI
	if (i < iNumSubsets) iCardSubset = 1 + oRandGen.nextInt(oItemList.size() - (iNumSubsets - i));
	else iCardSubset = oItemList.size();

	// GENERO I NUMERI DA INSERIRE NEL SOTTINSIEME
	for (j = 1; j <= iCardSubset; j++) {
		// PRENDO L'INDICE DI UN ELEMENTO A CASO E SCRIVO NEL FILE L'ELEMENTO CORRISPONDENTE A QUELL'INDICE
		iItemIndex = oRandGen.nextInt(oItemList.size());
		// RIMUOVO L'ELEMENTO DALLA LISTA
		oItemList.remove(iItemIndex);
	}
}

Ok, ho a fuoco il problema. Il modo in cui procedi nella creazione dei sottoinsiemi e dell'assegnazione degli oggetti è corretto. Il problema, secondo me, sta nel fatto che il random ti genera numeri alti nei primi cicli, così da dover inserire pochi oggetti nei sottoinsiemi rimanenti. Mi sa tanto che non puoi farci molto purtroppo.

[wingman87]

Questo sarebbe quello che intendevo:

/*
items: tutti gli oggetti (è una lista)
subsets: è un array di liste e ogni lista rappresenta un sottoinsieme
*/

//Disordina gli oggetti
Collections.shuffle(items);

//Metto un elemento in ogni sottoinsieme
for (i = 0; i < subsets.length; i++) {
   subsets[i].add(items.remove(0));
}

Random rand=new Random();
//Metto gli elementi rimanenti dentro a dei sottoinsiemi casuali
while(!items.isEmpty()){
   int index=rand.nextInt(subsets.length);
   subsets[index].add(items.remove(0));
}

[VegetaSSJ5]

Originariamente inviato da pernacentus

Ok, ho a fuoco il problema. Il modo in cui procedi nella creazione dei sottoinsiemi e dell'assegnazione degli oggetti è corretto. Il problema, secondo me, sta nel fatto che il random ti genera numeri alti nei primi cicli, così da dover inserire pochi oggetti nei sottoinsiemi rimanenti. Mi sa tanto che non puoi farci molto purtroppo.

in effetti anch'io sono arrivato a questa conclusione... stavo pensando di cambiare la creazione delle cardinalità dei sottoinsiemi partendo da un numero medio e facendo un + o - 50% ad esempio...

Originariamente inviato da wingman87

Questo sarebbe quello che intendevo:

/*
items: tutti gli oggetti (è una lista)
subsets: è un array di liste e ogni lista rappresenta un sottoinsieme
*/

//Disordina gli oggetti
Collections.shuffle(items);

//Metto un elemento in ogni sottoinsieme
for (i = 0; i < subsets.length; i++) {
   subsets[i].add(items.remove(0));
}

Random rand=new Random();
//Metto gli elementi rimanenti dentro a dei sottoinsiemi casuali
while(!items.isEmpty()){
   int index=rand.nextInt(subsets.length);
   subsets[index].add(items.remove(0));
}

questa mi sembra un'ottima idea.
appena la implemento di faccio sapere...

[VegetaSSJ5]

wingman ho implementato la soluzione che hai suggerito e devo dire che funziona molto bene. ora la cardinalità dei sottoinsiemi è molto più uniforme....
posto qui il pezzo di codice

// CREAZIONE LISTA DI SUPPORTO CONTENENTE GLI OGGETTI
ArrayList<Integer> oItemList = new ArrayList<Integer>();
for (i = 1; i <= iInstNumItems; i++) oItemList.add(new Integer(i));

// DISORDINA GLI ELEMENTI
Collections.shuffle(oItemList);

ArrayList[] oSubsetList = new ArrayList[iInstNumSubsets];
for (i = 0; i < iInstNumSubsets; i++) oSubsetList[i] = (new ArrayList());

// METTO UN ELEMENTO IN OGNI SOTTOINSIEME
for (i = 0; i < oSubsetList.length; i++) oSubsetList[i].add(oItemList.remove(0));

// METTO GLI ELEMENTI RIMANENTI DENTRO SOTTOINSIEMI CASUALI
while(!oItemList.isEmpty()) {
	i = oRandGen.nextInt(oSubsetList.length);
	oSubsetList[i].add(oItemList.remove(0));
}

// SCRIVO I SOTTOINSIEMI NEL FILE
oFileWriter.write("set CLASSES[<i> in SUBSET] := ");
for (i = 0; i < oSubsetList.length; i++) {
	if (i != 0) oFileWriter.write(",");
	oFileWriter.write("<" + (i+1) + ">");
	while(!oSubsetList[i].isEmpty()) {
		oFileWriter.write(oSubsetList[i].remove(0).toString());
		if (oSubsetList[i].size() > 0) oFileWriter.write(",");
	}
	if ((i+1) == oSubsetList.length) oFileWriter.write(";");
}

ora c'è solo un piccolo problemino logistico: quando compilo mi dà dei warning:

C:\Users\Armando\Documents\NetBeansProjects\TEST\src\test\Main.java:96: warning: [unchecked] unchecked call to add(E) as a member of the raw type java.util.ArrayList
            for (i = 0; i < oSubsetList.length; i++) oSubsetList[i].add(oItemList.remove(0));
                                                                       ^
C:\Users\Armando\Documents\NetBeansProjects\TEST\src\test\Main.java:101: warning: [unchecked] unchecked call to add(E) as a member of the raw type java.util.ArrayList
                oSubsetList[i].add(oItemList.remove(0));
                                  ^
2 warnings

ho eliminato il warning anche nella riga seguente specificando i tipi degli oggetti.

ArrayList<Integer> oItemList = new ArrayList<Integer>();

come posso evitare questi warning anche negli array? grazie!

[wingman87]

Puoi eliminarli usando:
ArrayList<Integer>[] oSubsetList =new ArrayList[iInstNumSubsets];
invece di:
ArrayList[] oSubsetList =new ArrayList[iInstNumSubsets];

Però in questo modo avrai un warning proprio su questa riga. Purtroppo non credo che si possa eliminare questo warning in modo pulito.

Puoi fare in modo che non ti venga più notificato aggiungendo
@SuppressWarning("unchecked")
Sopra alla firma del metodo.

Un'altro modo è usare un ArrayList invece di un array nativo, però in questo modo, secondo me, il codice perde in leggibilità.

Al momento non mi viene in mente altro.

[VegetaSSJ5]

ho usato il suppress warning...
ti ringrazio!