Algoritmi Lazy Shuffle

Question

Ho una lunga lista di elementi che voglio ripetere in ordine casuale. Tuttavia, non posso modificare l'elenco e non voglio nemmeno crearne una copia, perché 1) è grande e 2) ci si può aspettare che l'iterazione venga cancellata anticipatamente.

List<T> data = ...; 
Iterator<T> shuffled = shuffle(data); 
while (shuffled.hasNext()) { 
    T t = shuffled.next(); 
    if (System.console().readLine("Do you want %s?", t).startsWith("y")) { 
     return t; 
    } 
} 
System.out.println("That's all"); 
return t; 

Sto cercando un algoritmo erano il codice di cui sopra verrebbe eseguito nel O(n) (e preferibilmente richiedono solo O(log n) spazio), in modo caching gli elementi che sono stati prodotti in precedenza non è un'opzione. Non mi interessa se l'algoritmo è distorto (a patto che non sia ovvio).

(I utilizza pseudo-Java nella mia interrogazione, ma è possibile utilizzare altre lingue, se lo si desidera)

Qui è la migliore che ho avuto finora.

Iterator<T> shuffle(final List<T> data) { 
    int p = data.size(); 
    while ((data.size() % p) == 0) p = randomPrime(); 
    return new Iterator<T>() { 
     final int prime = p; 
     int n = 0, i = 0; 
     public boolean hasNext() { return i < data.size(); } 
     public T next() { 
      i++; n += prime; 
      return data.get(n); 
     } 
    } 
} 

Iterando tutti gli elementi O(n), spazio costante, ma ovviamente polarizzati in quanto può produrre solo data.size() permutazioni.

Answer 1

Gli approcci shuffling più facili che conosca funzionano con gli indici. Se lo List non è un ArrayList, si può finire con un algoritmo molto inefficiente se si tenta di utilizzare uno dei seguenti (uno LinkedList ha un get per ID, ma è O (n), quindi si finirà con O (n^2) tempo).

Se O (n) spazio va bene, cosa che presumo non lo è, io raccomanderei il Fisher-Yates/Knuth shuffle, è O (n) ora ed è facile da implementare. È possibile ottimizzarlo in modo che sia necessario eseguire una singola operazione prima di poter ottenere il primo elemento, ma è necessario tenere traccia del resto dell'elenco modificato man mano che si procede.

La mia soluzione:

Ok, quindi questo non è molto casuale a tutti, ma non riesco a vedere un modo migliore se si vuole meno di O (n) spazio.

Richiede O (1) spazio e O (n) tempo.

Potrebbe esserci un modo per aumentare leggermente l'utilizzo dello spazio e ottenere risultati più casuali, ma non l'ho ancora capito.

Ha a che fare con relative primes. L'idea è che, dati 2 numeri primi relativi a (il generatore) e b, quando si esegue il ciclo attraverso a % b, 2a % b, 3a % b, 4a % b, ..., vedrai ogni intero 0, 1, 2, ..., b-2, b-1, e questo avverrà anche prima di vedere qualsiasi numero intero due volte. Sfortunatamente non ho un link a una dimostrazione (il link di wikipedia potrebbe menzionarlo o implicarlo, non ho controllato troppo nei dettagli).

Comincio aumentando la lunghezza fino a ottenere un numero primo, poiché ciò implica che qualsiasi altro numero sarà un numero primo relativo, che è molto meno limitante (e basta saltare un numero maggiore della lunghezza originale), quindi generare un numero casuale e utilizzarlo come generatore.

Sto iterando e stampando tutti i valori, ma dovrebbe essere abbastanza facile da modificare per generare il successivo dato quello corrente.

Nota sto saltare 1 e len-1 con la mia nextInt, dal momento che questi produrranno 1,2,3,... e ...,3,2,1 rispettivamente, ma è possibile includere questi, ma probabilmente non se la lunghezza è al di sotto di una certa soglia.

Si potrebbe anche voler generare un numero casuale per moltiplicare il generatore per (mod la lunghezza) da cui iniziare.

codice Java:

static Random gen = new Random(); 

static void printShuffle(int len) 
{ 
    // get first prime >= len 
    int newLen = len-1; 
    boolean prime; 
    do 
    { 
    newLen++; 
    // prime check 
    prime = true; 
    for (int i = 2; prime && i < len; i++) 
     prime &= (newLen % i != 0); 
    } 
    while (!prime); 

    long val = gen.nextInt(len-3) + 2; 
    long oldVal = val; 
    do 
    { 
    if (val < len) 
     System.out.println(val); 
    val = (val + oldVal) % newLen; 
    } 
    while (oldVal != val); 
} 

Answer 2

Si può provare a utilizzare un buffer per farlo. Scorrere una serie limitata di dati e inserirla in un buffer. Estrarre valori casuali da quel buffer e inviarlo all'output (o ovunque ne abbiate bisogno). Passare al set successivo e continuare a sovrascrivere questo buffer. Ripeti questo passaggio.

Finiremo con le operazioni n + n, che è ancora O (n). Sfortunatamente, il risultato non sarà in realtà casuale. Sarà vicino a caso se si sceglie la dimensione del buffer correttamente.

Su una nota diversa, controllare questi due: Python - run through a loop in non linear fashion, random iteration in Python

Forse c'è un più elegante algoritmo per farlo meglio. Non sono sicuro però. In attesa di altre risposte in questa discussione.

Answer 3

Questa non è una risposta perfetta alla tua domanda, ma forse è utile.

L'idea è quella di utilizzare un generatore di numeri casuali reversibile e l'algoritmo di mescolamento basata matrice solito svolto pigramente: per ottenere il i 'th articolo mescolate, scambiare a[i] con e scelto a caso a[j] dove j è in [i..n-1], poi ritorno a[i]. Questo può essere fatto nell'iteratore.

Dopo aver terminato l'iterazione, reimpostare l'array nell'ordine originale "svitando" utilizzando la direzione inversa del RNG.

Il reset di una riorganizzazione non richiederà mai più tempo dell'iterazione originale, quindi non cambia il costo asintotico. L'iterazione è ancora lineare nel numero di iterazioni.

Come costruire un RNG reversibile? Basta usare un algoritmo di crittografia. Cripta il valore pseudo-casuale precedentemente generato per andare avanti, e decrittalo per andare indietro. Se si dispone di un algoritmo di crittografia simmetrica, è possibile aggiungere un valore "salato" ad ogni passaggio in avanti per impedire un ciclo di due e sottrarlo per ogni passo indietro. Lo dico perché RC4 è semplice, veloce e simmetrico. L'ho usato prima per compiti come questo. Crittografare i valori a 4 byte e calcolare il mod per farli entrare nell'intervallo desiderato sarà davvero veloce.

È possibile premere questo nel pattern iteratore Java estendendo Iterator per consentire reimpostazioni. Vedi sotto. L'utilizzo sarà simile a:

ShuffledList<Integer> lst = new SuffledList<>(); 

... build the list with the usual operations 

ResetableInterator<Integer> i = lst.iterator(); 
while (i.hasNext()) { 
    int val = i.next(); 

    ... use the randomly selected value 

    if (anyConditinoAtAll) break; 
} 
i.reset(); // Unshuffle the array 

So che questo non è perfetto, ma sarà veloce e darà un buon shuffle. Notare che se non si esegue reset, l'iteratore successivo sarà ancora un nuovo casuale casuale, ma l'ordine originale verrà perso per sempre. Se il corpo del loop può generare un'eccezione, è necessario eseguire il ripristino in un blocco finally.

class ShuffledList<T> extends ArrayList<T> implements Iterable<T> { 

    @Override 
    public Iterator<T> iterator() { 
     return null; 
    } 

    public interface ResetableInterator<T> extends Iterator<T> { 
     public void reset(); 
    } 

    class ShufflingIterator<T> implements ResetableInterator<T> { 

     int mark = 0; 

     @Override 
     public boolean hasNext() { 
      return true; 
     } 

     @Override 
     public T next() { 
      return null; 
     } 

     @Override 
     public void remove() { 
      throw new UnsupportedOperationException("Not supported."); 
     } 

     @Override 
     public void reset() { 
      throw new UnsupportedOperationException("Not supported yet."); 
     } 
    } 
}