Creare una permutazione casuale di 1..N nello spazio costante

Question

Sto cercando di elencare una permutazione casuale dei numeri 1..N nello spazio fisso. Ciò significa che non posso memorizzare tutti i numeri in una lista. Il motivo è che N può essere molto grande, più della memoria disponibile. Voglio ancora essere in grado di camminare attraverso una tale permutazione dei numeri uno alla volta, visitando ogni numero esattamente una volta.

So che questo può essere fatto per alcuni N: Molti generatori di numeri casuali attraversano a caso tutto il loro stato, ma interamente. Un buon generatore di numeri casuali con dimensione di stato di 32 bit emetterà una permutazione dei numeri 0 .. (2^32) -1. Ogni numero esattamente una volta.

Voglio arrivare a scegliere N per essere un numero qualsiasi e non essere vincolato alle potenze di 2 per esempio. C'è un algoritmo per questo?

Answer 1

Il modo più semplice è probabilmente quello di creare un PRNG a gamma intera per un intervallo più ampio di quello a cui tieni, e quando genera un numero più grande di quello che vuoi, buttalo via e prendi quello successivo.

Un'altra possibilità che è praticamente una variazione dello stesso sarebbe utilizzare un registro di spostamento di feedback lineare (LFSR) per generare i numeri in primo luogo. Questo ha un paio di vantaggi: prima di tutto, un LFSR è probabilmente un po 'più veloce della maggior parte dei PRNG. In secondo luogo, è (credo) un po 'più facile progettare un LFSR che produce numeri vicini all'intervallo desiderato, ed essere sicuri che passi ciclicamente attraverso i numeri nel suo intervallo in ordine casuale (pseudo), senza alcuna ripetizione.

Senza dedicare molto tempo ai dettagli, la matematica degli LFSR è stata studiata in modo approfondito. Produrre uno che attraversa tutti i numeri della sua gamma senza ripetizione richiede semplicemente la scelta di un insieme di "rubinetti" che corrispondono a un polinomio irriducibile. Se non vuoi cercarlo da solo, è abbastanza facile trovare tabelle di quelle conosciute per quasi tutte le dimensioni ragionevoli (ad esempio, facendo un rapido sguardo, l'articolo di wikipedia le elenca per dimensioni fino a 19 bit).

Se la memoria serve, c'è almeno un polinomio irriducibile con dimensioni di bit sempre possibili. Ciò si traduce nel caso in cui nel caso peggiore si possa creare un generatore che ha all'incirca il doppio dell'intervallo di cui si ha bisogno, quindi in media si sta buttando via (all'incirca) ogni altro numero generato. Data la velocità di un LFSR, direi che puoi farlo e mantenere una velocità abbastanza accettabile.

Answer 2

Un modo per farlo sarebbe

1. Trova un numero primo più grande di pN, preferibilmente non molto più grande.
2. trovare una radice primitiva dell'unità g modulo p, cioè un numero tale che 1 < g < pg^k ≡ 1 (mod p) se e solo se k è un multiplo di p-1.
3. Passare attraverso g^k (mod p) per k = 1, 2, ..., ignorando i valori superiori a N.

Per ogni primo p, ci sono φ(p-1) radici primitive di unità, quindi funziona. Tuttavia, potrebbe volerci un po 'per trovarne uno. Trovare un ottimo adatto è molto più semplice in generale.

Per trovare una radice primitiva, non conosco nulla di sostanzialmente migliore rispetto a tentativi ed errori, ma si può aumentare la probabilità di una ricerca rapida scegliendo il valore ottimale p in modo appropriato.

Poiché il numero di radici primitive è φ(p-1), se si sceglie a caso r nel range da 1 a p-1, il numero atteso di tentativi finché si trova una radice primitiva è (p-1)/φ(p-1), quindi si dovrebbe scegliere p modo che φ(p-1) relativamente sia di grandi dimensioni, ciò significa che p-1 deve avere pochi distinti primi divisori (e preferibilmente solo di grandi dimensioni, ad eccezione del fattore 2).

Invece di modo casuale la scelta, si può anche provare in sequenza se 2, 3, 5, 6, 7, 10, ... è una radice primitiva, ovviamente saltare poteri perfetti (o non, sono, in generale, rapidamente eliminato), che non dovrebbe influenzare il numero di tentativi necessari notevolmente.

Quindi si riduce a verificare se un numero x è una radice primitiva modulo p. Se p-1 = q^a * r^b * s^c * ... con primi distinti q, r, s, ..., x è una radice primitiva se e solo se

x^((p-1)/q) % p != 1 
x^((p-1)/r) % p != 1 
x^((p-1)/s) % p != 1 
... 

quindi è necessario un elevamento modulare discreto (esponenziale mediante ripetute quadratura si presta bene che, riducendo dal modulo ad ogni passo). E un buon metodo per trovare la decomposizione del primo fattore di p-1. Si noti, tuttavia, che anche la divisione di prova ingenua sarebbe solo O (√ p), mentre la generazione della permutazione è Θ (p), quindi non è fondamentale che la fattorizzazione sia ottimale.

Answer 3

Un altro modo per farlo è con un codice a blocchi; vedi this blog post per dettagli.

Il blog contiene collegamenti al documento Ciphers with Arbitrary Finite Domains che contiene un sacco di soluzioni.

Answer 4

consideri il primo 3. Per esprimere appieno tutte le uscite possibili, pensare in questo modo ...

bias + step mod prime 

Il bias è solo un pregiudizio offset. step è un accumulatore (se è 1 ad esempio, sarebbe solo 0, 1, 2 in sequenza, mentre 2 risulterebbe in 0, 2, 4) e prime è il numero primo su cui vogliamo generare le permutazioni.

Ad esempio. Una semplice sequenza di 0, 1, 2 sarebbe ...

0 + 0 mod 3 = 0 
0 + 1 mod 3 = 1 
0 + 2 mod 3 = 2 

Modifica di un paio di quelle variabili per un secondo, prenderemo bias di 1 e step di 2 (solo per l'illustrazione) ...

1 + 2 mod 3 = 0 
1 + 4 mod 3 = 2 
1 + 6 mod 3 = 1 

Noterete che abbiamo prodotto una sequenza completamente diversa. Nessun numero all'interno del set si ripete e tutti i numeri sono rappresentati (è bidirezionale). Ogni combinazione unica di offset e bias comporterà una delle possibili permutazioni del set di prime!. Nel caso di un prime di 3 vedrete che ci sono diversi 6 permuations possibili:

0,1,2 
0,2,1 
1,0,2 
1,2,0 
2,0,1 
2,1,0 

Se fate i conti sulle variabili di cui sopra non sarete che si traduce negli stessi obblighi di informazione .. .

1/3! = 1/6 = 1.66.. 

... vs ...

1/3 (bias) * 1/2 (step) => 1/6 = 1.66.. 

Restrizioni sono semplici, bias deve essere all'interno di 0..P-1 e step deve essere entro 1..P-1 (mi è stato funzionale solo usando 0..P-2 e aggiungendo 1 sull'aritmetica nel mio lavoro). Oltre a questo, funziona con tutti i numeri primi, non importa quanto grande e permuterà tutti i possibili set di questi senza la necessità di memoria oltre un paio di interi (ognuno richiede tecnicamente meno bit del primo stesso).

Nota con attenzione che questo generatore non è destinato a essere utilizzato per generare insiemi che non sono in numero primo. È del tutto possibile farlo, ma non è raccomandato per scopi di sicurezza in quanto introdurrebbe un attacco di temporizzazione.

Detto questo, se si desidera utilizzare questo metodo per generare una sequenza di insiemi che non è un numero primo, si hanno due scelte.

Primo (e il più semplice/più economico), scegli il numero primo più grande della dimensione impostata che stai cercando e fai in modo che il generatore scarti semplicemente tutto ciò che non appartiene. Ancora una volta, pericolo, questa è una pessima idea se si tratta di un'applicazione sensibile alla sicurezza.

Secondo (di gran lunga il più complicato e costoso), è possibile riconoscere che tutti i numeri sono composti da numeri primi e creano più generatori che quindi producono un prodotto per ciascun elemento dell'insieme. In altre parole, lo 6n implicherebbe tutti i possibili generatori di primi che potrebbero corrispondere a 6 (in questo caso, 2 e 3), moltiplicato in sequenza. Questo è sia costoso (anche se matematicamente più elegante) e presenta anche un attacco di temporizzazione quindi è ancora meno consigliato.

Infine, se è necessario un generatore per bias eo step ... perché non si utilizza un altro della stessa famiglia :). All'improvviso sei estremamente vicino alla creazione di veri campioni semplici-casuali (che di solito non sono facili).

Answer 5

La debolezza fondamentale degli LCG (generatori di stile x=(x*m+c)%b) è utile qui.

Se il generatore è correttamente formata quindi x%f è anche una sequenza ripetitiva di tutti i valori inferiori f (disponibile f se un fattore di b).

Poiché b è in genere una potenza pari a 2, ciò significa che è possibile utilizzare un generatore a 32 bit e ridurlo a un generatore di n bit mascherando i bit superiori e avrà la stessa proprietà dell'intero intervallo.

Ciò significa che è possibile ridurre il numero di valori di scarto in modo che sia inferiore a N scegliendo una maschera appropriata.

Sfortunatamente LCG è un generatore povero esattamente per la stessa ragione indicata sopra.

Inoltre, questo ha esattamente la stessa debolezza che ho notato in un commento sulla risposta di @JerryCoffin. Produrrà sempre la stessa sequenza e l'unica cosa che i controlli seme sono da dove iniziare in quella sequenza.

Answer 6

Ecco alcuni SageMath che dovrebbe generare una permutazione casuale il modo Daniel Fischer suggested:

def random_safe_prime(lbound): 
    while True: 
     q = random_prime(lbound, lbound=lbound // 2) 
     p = 2 * q + 1 
     if is_prime(p): 
      return p, q 


def random_permutation(n): 
    p, q = random_safe_prime(n + 2) 

    while True: 
     r = randint(2, p - 1) 
     if pow(r, 2, p) != 1 and pow(r, q, p) != 1: 
      i = 1 
      while True: 
       x = pow(r, i, p) 
       if x == 1: 
        return 

       if 0 <= x - 2 < n: 
        yield x - 2 

       i += 1