1
$\begingroup$

A couple of friends and I were talking about the best way to attempt to shuffle a infinite list, given finite memory. We immediately concluded that you could not do so, at least not in the same sense that you could shuffle a finite list. But we devised an approximation.

Initialize: Draw from the infinite list $L$, a array of items $W$ which we will call the window, of size $w$ items ($w\in\mathbb{Z}$)

Output To output an element from our shuffled list:

  1. $i\leftarrow rand(0:w)$ -- Generate a random integer $i$, with $0\le i < w$
  2. $r\leftarrow W[i]$ -- select the item to return
  3. $W[i]\leftarrow head(L)$ -- replace it with the first item in the infinite list
  4. $L\leftarrow tail(L)$ -- remove that item that we took
  5. Output $r$

So the basic idea is that we give a random item from a finite window, which we take with replacement from the infinite list.

Now I am sure this is not a new idea. So I am looking for a name for it, so I can look into it and read up on its properties. Eg it is clear that by increasing $w$ increases the "entropy" in some sense. But I am not sure if for a fixed $w$ if over time it converges to a steady state for the expected positional distance between adjacent output items.

Also so that if I end up implementing and using it in my current work, I can cite the right paper.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.