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.


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.