L'idea di un generatore casuale che simula uno shuffle è buona se è possibile ottenerne uno il cui periodo massimo è possibile controllare.
Un Linear Congruential Generator calcola un numero casuale con la formula:
x[i + 1] = (a * x[i] + c) % m;
La durata massima è m e viene raggiunto quando le seguenti propriet'a:
- I parametri c e m sono relativamente primi.
- Per ogni numero primo r dividendo m, un-1 è un multiplo di r.
- Se m è un multiplo di 4 poi anche un-1 è multiplo di 4.
Il mio primo darft interessate che esprimono m il prossimo multiplo di 4, dopo la lunghezza della matrice e poi trovare adatto a e c valori. Questo è stato (a) un sacco di lavoro e (b) ha prodotto risultati molto ovvi a volte.
Ho ripensato questo approccio. Possiamo fare m il più piccolo potere di due che la lunghezza dell'array si adatterà. L'unico fattore primo di m è quindi 2, che renderà ogni numero dispari relativamente primo ad esso. Con l'eccezione di 1 e 2, m saranno divisibile per 4, che significa che dobbiamo un - 1 A multiplo di 4.
Avendo una maggiore m rispetto alla lunghezza dell'array significa che noi deve scartare tutti i valori che sono indici di array illegali. Ciò avverrà al massimo ogni altro turno e dovrebbe essere trascurabile.
Il seguente codice produce numeri pseudo casuali con un periodo di precisione m. Ho evitato valori insignificanti per a e c e sul mio punto di vista (non troppo numeroso), i risultati sembravano a posto. Almeno non c'era un modello ciclico ovvio.
Quindi:
class RandomIndexer
{
public:
RandomIndexer(size_t length) : len(length)
{
m = 8;
while (m < length) m <<= 1;
c = m/6 + uniform(5 * m/6);
c |= 1;
a = m/12 * uniform(m/6);
a = 4*a + 1;
x = uniform(m);
}
size_t next()
{
do { x = (a*x + c) % m; } while (x >= len);
return x;
}
private:
static size_t uniform(size_t m)
{
double p = std::rand()/(1.0 + RAND_MAX);
return static_cast<int>(m * p);
}
size_t len;
size_t x;
size_t a;
size_t c;
size_t m;
};
È quindi possibile utilizzare il generatore in questo modo:
std::vector<int> list;
for (size_t i = 0; i < 3; i++) list.push_back(i);
RandomIndexer ix(list.size());
for (size_t i = 0; i < list.size(); i++) {
std::cout << list[ix.next()]<< std::endl;
}
Sono consapevole che questo ancora non è un grande generatore di numeri casuali, ma è ragionevolmente veloce, non richiede una copia dell'array e sembra funzionare bene.
Se l'approccio di raccogliere un e c casualmente produce cattivi risultati, potrebbe essere una buona idea per limitare il generatore ad alcune potenze di due ed a valori di letteratura hard-code che hanno dimostrato di essere buono.
Sei felice di visitare un determinato elemento più di una volta o no? cioè stai cercando una permutazione casuale degli elementi o una sequenza casuale di elementi? La domanda che stai citando riguarda il primo di questi problemi (noto anche come shuffling). – Walter
Molti (molti?) Generatori di numeri pseudo casuali possono essere definiti da un algoritmo e da un intero o due per descrivere il loro stato corrente. Dati questi fattori, il loro comportamento futuro è del tutto deterministico, anche se apparentemente casuale - questo è ciò che * pseudo * significa qui. Cosa stai cercando non è un PRNG? –
Ovviamente, ho bisogno di evitare ripetizioni (altrimenti posso passare direttamente all'elemento casuale molto tempo). Ho modificato la domanda aggiungendo quell'informazione. Infatti, la soluzione desiderata dovrebbe memorizzare lo stato corrente in un modo che permetta di attraversare N elementi in N passi da qualsiasi stato. – Michal