numeri random distinti

[mascalzone]

ciao a tutti,

avrei bisogno diriempire un array con tutti numeri interi generati random e distinti

non riesco a scrivere un generatore di numeri casuali distinti...

chi mi può aiutare?

[LordSaga640]

Se sono casuali come fai a farli distinti?

Io la butto li...

Invece di inserire in un array puoi usare una tabella hash oun albero binario bilanciato e fare gli inserimenti ordinati. Se il numero è gia presente lo scarti e passi al prossimo. Se i numeri sono pochi usi l'array e fai una ricerca lineare per vedere se è gia presente.

Ciao ^^

[mascalzone]

ehmm
mi serve il contrario
mi serve un array non ordinato con valori distinti
per implementare e testare un algoritmo Randomized-Select

non vorrei avere una complessità mostruosa solo per ottenere l'Array di input :P

[LordSaga640]

Come lo vedi di usare due strutture dati?

Una tabella hash che usi solo per inserire i numeri e vedere se sono gia presenti e l'array per inserire i numeri appena generati.

la complessità per generare n numeri random è quasi O(n) come limite inferiore. Usi un po' più di memoria... però la performance dovresti comunque averla.

[mascalzone]

si una complessità O(n) va benone...
quindi se ho capito bene
diciamo che a me serve riempire un array di 1000 elementi tutti distinti e non ordinati

faccio una tabe hash di 1000 elemnti in modo che sono sicuro che siano distinti e poi riempio l'array?
ho capito bene?

se si va benone....ma non some fare in Java...la tabella hash con 1000 elementi tutti distinti e poi scorrerla
stavo leggendo che ci sono delle classi HashSet....ma chi ci capisce :P

[mascalzone]

ho risolto così

	static void RandomizedInPlace ( int[] A ){
		java.util.Random casuale = new java.util.Random();
		int n = A.length;
		int appoggio, random;
		for(int i=0; i < A.length; i++){
			random = (casuale.nextInt(n-i))+i;
			appoggio = A[i];
			A[i] = A[random];
			A[random] = appoggio;
		}
	}


	for(int i=0; i < A.length; i++) A[i]=i;
	RandomizedInPlace(A);

dite che funziona?

[LordSaga640]

stavo chiudendo il browser quando ho visto che hai risposto.

Non ho letto il codice ma ti riassumo brevemente quello che...secondo me dovresti fare.

Il package java.util.* contiene le strutture dati più comunemente usate (molto ottimizzate).

Quella che ti serve a te è la hashset, cioè una tabella hash nel quale puoi inserire solo valore fregandotene della chiave. La hashset è solo un insieme di valore. La cosa interessante è che le operazioni quali inserimento, cancellazione, controllo della presenza sono molto performanti.

L'hashset non c'è bisogno che lo fai di mille posizioni. Aumenta automaticamente la sua capacità quando ci sono pochi spazzi disponibili. (in genera 1/4 dei posti deve essere libero).
Se sai gia inizialmente quanti elementi avrai puoi inizializzare l'hashset ad una tua dimensione grazie al costruttore:
HashSet(int initialCapacity)
Se devi aggiungere N elementi, crea un hash di N + N/2 .

L'hash set accetta solo puntatori ad oggetti quindi usa Integer per salvare i tuoi interi.
miohashset->add(new Integer(numero));

Semplicemente cosa farai? Generi un numero casuale, controlli se non è nella tabella hash. Se è presenti generi un nuovo numero. Se non è presente aggiungi questo numero nella tabella hash e nell'array.

Chiaro?