Generazione della gamma mescasting usando un PRNG piuttosto che shuffling

Esiste un algoritmo noto in grado di generare un intervallo shuffled [0..n) in tempo lineare e spazio costante (quando l’output è prodotto in modo iterativo), dato un valore di seme arbitrario?

Supponiamo che n possa essere grande, ad esempio nei molti milioni, quindi non è richiesto il requisito di produrre potenzialmente ogni ansible permutazione, non ultimo perché è imansible (lo spazio del valore seme dovrebbe essere enorme). Questo è anche il motivo per un requisito di spazio costante. (Quindi, in particolare, non sto cercando un algoritmo di shuffling array, in quanto richiede che l’intervallo sia memorizzato in una matrice di lunghezza n, e quindi utilizzerebbe lo spazio lineare.)

Sono a conoscenza della domanda 162606 , ma non presenta una risposta a questa particolare domanda: le mappature dagli indici di permutazione alle permutazioni date in quella domanda richiederebbero un enorme spazio di valore seme.

Idealmente, si comporterebbe come un LCG con un periodo e un intervallo di n , ma l’arte di selezionare a e c per un LCG è sottile. Semplicemente soddisfacendo i vincoli di a e c in un periodo di piena validità LCG può soddisfare le mie esigenze, ma mi chiedo se ci sono idee migliori là fuori.

Sulla base della risposta di Jason , ho realizzato un’implementazione semplice e semplice in C #. Trova la potenza successiva più grande di due maggiore di N. Questo rende banale generare aec, dato che c deve essere relativamente primo (il che significa che non può essere divisibile per 2, altrimenti dispari), e (a-1) ha bisogno essere divisibile per 2, e (a-1) deve essere divisibile per 4. Statisticamente, occorrono 1-2 congruenze per generare il numero successivo (dal 2N> = M> = N).

 class Program { IEnumerable GenerateSequence(int N) { Random r = new Random(); int M = NextLargestPowerOfTwo(N); int c = r.Next(M / 2) * 2 + 1; // make c any odd number between 0 and M int a = r.Next(M / 4) * 4 + 1; // M = 2^m, so make (a-1) divisible by all prime factors, and 4 int start = r.Next(M); int x = start; do { x = (a * x + c) % M; if (x < N) yield return x; } while (x != start); } int NextLargestPowerOfTwo(int n) { n |= (n >> 1); n |= (n >> 2); n |= (n >> 4); n |= (n >> 8); n |= (n >> 16); return (n + 1); } static void Main(string[] args) { Program p = new Program(); foreach (int n in p.GenerateSequence(1000)) { Console.WriteLine(n); } Console.ReadKey(); } } 

Ecco una implementazione Python del Generatore di Congruenza Lineare dalla risposta di FryGuy . Perché avevo bisogno di scriverlo comunque e ho pensato che potesse essere utile per gli altri.

 import random import math def lcg(start, stop): N = stop - start # M is the next largest power of 2 M = int(math.pow(2, math.ceil(math.log(N+1, 2)))) # c is any odd number between 0 and M c = random.randint(0, M/2 - 1) * 2 + 1 # M=2^m, so make (a-1) divisible by all prime factors and 4 a = random.randint(0, M/4 - 1) * 4 + 1 first = random.randint(0, M - 1) x = first while True: x = (a * x + c) % M if x < N: yield start + x if x == first: break if __name__ == "__main__": for x in lcg(100, 200): print x, 

Sembra che tu voglia un algoritmo che è garantito per produrre un ciclo da 0 a n-1 senza alcuna ripetizione. Ci sono quasi certamente un sacco di questi a seconda delle tue esigenze; la teoria dei gruppi sarebbe il ramo più utile della matematica se si vuole approfondire la teoria alla base.

Se vuoi veloce e non ti preoccupi della prevedibilità / sicurezza / modelli statistici, un LCG è probabilmente l’approccio più semplice. La pagina di wikipedia che hai collegato contiene questo (abbastanza semplice) insieme di requisiti:

Il periodo di un LCG generale è al massimo m, e per alcune scelte di molto inferiore. Il LCG avrà un periodo completo se e solo se:

  1. c e m sono relativamente primi,
  2. a – 1 è divisibile per tutti i fattori primi di m
  3. a – 1 è un multiplo di 4 se m è un multiplo di 4

In alternativa, puoi scegliere un periodo N> = n, dove N è il valore più piccolo che ha proprietà numeriche convenienti e semplicemente scartare qualsiasi valore prodotto tra n e N-1. Ad esempio, il più basso N = 2 k – 1> = n consente di utilizzare registri di spostamento di feedback lineare (LFSR). Oppure trova il tuo algoritmo crittografico preferito (RSA, AES, DES, qualsiasi cosa) e, data una chiave particolare, calcola lo spazio N dei numeri che permuta e per ogni passaggio applica la crittografia una volta.

Se n è piccolo ma vuoi che la sicurezza sia alta, è probabilmente il caso più complicato, poiché ogni sequenza S è probabile che abbia un periodo N molto più alto di n, ma è anche non banale per derivare una sequenza di numeri non ripetitiva con un periodo più breve di N. (ad esempio, se si potesse prendere l’output di S mod n e garantire una sequenza non ripetitiva di numeri, ciò fornirebbe informazioni su S che un utente malintenzionato potrebbe utilizzare)

Vedi il mio articolo sulle permutazioni sicure con cifrari a blocchi per un modo per farlo.

Cerca nei registri a scorrimento lineare feedback, possono essere usati esattamente per questo. Il modo breve per spiegarle è che inizi con un seme e poi esegui l’iterazione usando la formula

 x = (x << 1) | f(x) 

dove f (x) può restituire solo 0 o 1.

Se scegli una buona funzione f , x scorrerà tra tutti i valori compresi tra 1 e 2 ^ n-1 (dove n è un certo numero), in un buon modo pseudo-casuale. Qui è ansible trovare funzioni di esempio, ad es. Per 63 valori che è ansible utilizzare

 f(x) = ((x >> 6) & 1) ^ ((x >> 5) & 1)