Shuffle / Randomize una collezione senza conoscere il numero di elementi? [chiuso]

Un modo comune di leggere i dati che arrivano nel computer è di bufferizzarli da uno streaming.

A volte gli stream hanno una lunghezza indefinita. Tutto quello che sappiamo per certo è che possiamo "ottenere il prossimo personaggio dal flusso".

Normalmente aggiungeremo il carattere dallo stream alla fine del buffer (si pensi alla coda FIFO).

La dimensione del buffer non deve necessariamente essere la dimensione del flusso, SE stiamo contemporaneamente svuotando il buffer (cioè, leggendo da esso per passare i dati da qualche altra parte) allo stesso tempo. Il tuo stream potrebbe produrre un singolo carattere alla volta, ma potresti volerli "bufferizzare" fino a quando non hai una linea completa. È possibile trasferire un file di testo da 100 MB attraverso un buffer da 1 KB finché nessuna riga singola nel file ha una lunghezza superiore a 1.024 caratteri.

Ecco il bit intelligente

Che succede se invece di aggiungere il prossimo carattere dallo stream alla fine del buffer , lo inseriamo casualmente in un punto qualsiasi del buffer?

Un'importante limitazione

Nessun elemento può essere spostato dalla sua posizione originale di più della dimensione del buffer. Se hai una dimensione del buffer di 200 e hai 1.000 elementi, non sceglierai mai "casualmente" l'elemento 999 ^th . Avere un buffer davvero grande aiuterebbe.

Idealmente, avere un buffer più grande del tuo flusso di input ridurrebbe questo a un problema molto più semplice.

Ecco uno di questi schemi. È solo una breve idea, non l'ho controllato attentamente per errori potenziali.

Prima di iniziare, eseguiamo la seguente configurazione:

• Per ogni numero naturale N (1, 2, 3, ...), scegli una funzione di bit shuffling per N bit.

Procedura per la conversione dell'interrogazione intero I alla risposta intero J

1. Data una query integer I , convertila in rappresentazione binaria.
2. Se il numero intero della query I è zero o uno, non c'è nulla da fare; restituirlo come J .
   • Questa è una limitazione di questo schema.
3. Trova il set di bit più alto (il bit più significativo che è un "uno"). Scegli N in modo che ci siano N cifre binarie sotto il set più alto di bit.
4. Cerca la funzione di mischiare il bit per N come configurato sopra.
5. Applica questa funzione di bit shuffling ai bit N più bassi del numero. Ricorda che il set più alto non viene mischiato; deve mantenere il suo valore di "uno".
6. Il nuovo numero (dove è conservato il set di bit più alto ma i bit più bassi sono stati mescolati) viene restituito come numero intero di risposta J .

Analisi.

• Supponiamo che la query intero I possa essere rappresentata in 6 cifre binarie. (esempio: "100101"). La massima risposta possibile integer J dato I è anche 6 cifre binarie (esempio: "111111"). Pertanto, il limite superiore per J è pow(2, ceil(log2(I + 1))) - 1 .

Affinamento richiesto dal commento di @ amon.

La funzione di permutazione bit a bit N-bit può essere sostituita da una generale funzione di permutazione integer 2**N (mappatura di interi one-to-one). In questo modo, quando gli N bit sono tutti zero, non sarà bloccato con un'uscita tutto-zero dovuta alla permutazione bit a bit.

Ci sono molte carenze in questo schema. Lo scopo di questa risposta è incoraggiare più discussioni e possibilmente risposte più pratiche.