[algoritmi] combinazioni uniche di numeri casuali

[Scara95]

Hai ragione scara. Comunque no... L'ordine non è importante.
penso che mi accontenterò di far si che ogni numero non si ripeta mai, mi sembra un buon compromesso

C'è sempre l'opzione di continuare a generare quadruple a caso e controllare se sono già state generate, ad esempio con un set di quadruple, che è l'adattamento della soluzione proposta da Alex'87

Certo non è efficientissima, ma è pur sempre una soluzione.

Inoltre generando numeri unici puoi arrivare ad un massimo 249 quadruple complete e 1 tripla, che non concorda con la possibilità di avere centinaia di quadruple uniche. Superato questo limite saresti comunque costretto a controllare di non averla già generata.

Certo puoi considerare anche una soluzione mista...

[sspintux]

Ci avevo pensato anch'io, ma si parla di quadruple uniche, che sarebbe un 999^4 numero di quadruple uniche....

Edit: approssimativamente 7,25 TB con interi a 2 bytes

Ciao,

mi chiedo se sia proprio necessario memorizzare tutte le 999^4 combinazioni ;
.... in fondo l'OP ha parlato di centinaia di quadruple distinte con numeri da 1 a 999 senza altri particolari vincoli.

Quindi con i numeri da 1 a 999 otterrebbe 999\4=249 quadruple con 249 estrazioni casuali di indici
(ed avanzerebbero ancora 3 numeri da giocarsi)

Se occorressero altre quadruple non potrebbe bastare scambiare
il primo numero della prima quadrupla con il primo della seconda, della terza ... etc ?

[Scara95]

Ciao,
Se occorressero altre quadruple non potrebbe bastare scambiare
il primo numero della prima quadrupla con il primo della seconda, della terza ... etc ?

A questo non avevo pensato!

[MegaAlchimista]

Oppure creo tutte le quadruple "uniche" e poi se me ne servono altre, scambio l'ordine dei numeri di quelle giá create!

[sspintux]

Oppure creo tutte le quadruple "uniche" e poi se me ne servono altre, scambio l'ordine dei numeri di quelle giá create!

... che è quello di cui si parlava.

P.S.
Non so che linguaggio usi , ma in ogni caso ti segnalo che per copiare array di interi , essendo memorizzati in posizioni
contigue di memoria, puoi usare una efficientissima copymemory.

HTH

[MegaAlchimista]

Lo sto implementando nel seguente modo:
-prenderò il numero di elementi da creare
-fino a 999li creo usando 4vettori, creando 999combinazioni sicuramente uniche dove ogni numero preso singolarmente non si ripete mai
-dall'oggetto con indice 999, copio l'oggetto (i-999) e tengo il primo numero fisso.
Per esempio se il primo oggetto che avevo creato era 10.1.1.1 ed il secondo 5.2.4.6 il millesimo sarà 1.1.1.1 , il 1001 sarà 1.2.4.6.
così creo i prossimi (999-1)*999 oggetti [-1 perchè per ogni ciclo esisterá una combinazione in cui quello è già il numero iniziale].

Se ancora non dovesse bastare lo farò con la seconda cifra, e così via.

In questo modo posso potenzialmente creare proprio tutte le combinazioni uniche di quattro interi.
Grazie a tutti per gli spunti, rimango aperto ad altre idee e suggerimenti

[MItaly]

Secondo me ti stai complicando inutilmente la vita.
Il tuo spazio delle combinazioni è 999^4, ovvero circa 10^12, sicuramente molto più grande del numero di oggetti che creerai; questo significa che il numero di collisioni atteso è estremamente basso (tu stesso hai detto che alla peggio creerai qualche centinaia di oggetti - il 10^12 non lo scalfisci nemmeno).

Per questo, io userei un brutale random sui quattro numeri per poi memorizzare la combinazione in un hashset (std::unordered_set); quando generi una nuova tupla di valori, controlli se è già stata estratta, e se non lo è ne generi un'altra. Questo metodo ha complessità temporale media O(1) (dato che, per le probabilità in ballo, la probabilità di un duplicato è essenzialmente nulla, e un lookup in hashtable è O(1)), e complessità spaziale O(n) - che non dovrebbe essere un problema, dato che il costo di ogni elemento in hashtable nel tuo caso dovrebbe essere al più 8 byte.

[MegaAlchimista]

Secondo me ti stai complicando inutilmente la vita.
Il tuo spazio delle combinazioni è 999^4, ovvero circa 10^12, sicuramente molto più grande del numero di oggetti che creerai; questo significa che il numero di collisioni atteso è estremamente basso (tu stesso hai detto che alla peggio creerai qualche centinaia di oggetti - il 10^12 non lo scalfisci nemmeno).

Per questo, io userei un brutale random sui quattro numeri per poi memorizzare la combinazione in un hashset (std::unordered_set); quando generi una nuova tupla di valori, controlli se è già stata estratta, e se non lo è ne generi un'altra. Questo metodo ha complessità temporale media O(1) (dato che, per le probabilità in ballo, la probabilità di un duplicato è essenzialmente nulla, e un lookup in hashtable è O(1)), e complessità spaziale O(n) - che non dovrebbe essere un problema, dato che il costo di ogni elemento in hashtable nel tuo caso dovrebbe essere al più 8 byte.

Hai ragione: io mi aspetto di creare un numero di oggetti che va da 10 a più di 2000. So che è niente in confronto a 999^4.
Per la precisione sto utilizzando C#, e ad essere sincero vengo da c++ e sono un po' alle prime armi con questo linguaggio.
Volendo seguirti potrei utilizzare System.Collection.Hashtable? E dovrei fare l'override di GetHashCode() alla mia classe?

[MItaly]

Uhm... a te interessa l'ordine in cui i punti sono memorizzati in container?

[MegaAlchimista]

No. Il mio container è un grafo, e questo oggetto con 4 interi funge da identificatore unico per ogni nodo