Just been having a play with this and realised that the Fisher-Yates shuffle works well "on-line". For example, if you've got a large list you don't need to spend the time to shuffle the whole thing before you start iterating over items, or, equivalently, you might only need a few items out of a large list.
I didn't see a language tag in the question, so I'll pick Python.
from random import randint def iterrand(a): """Iterate over items of a list in a random order. Additional items can be .append()ed arbitrarily at runtime.""" for i, ai in enumerate(a): j = randint(i, len(a)-1) a[i], a[j] = a[j], ai yield a[i] This is O(n) in the length of the list and by allowing .append()s (O(1) in Python) the list can be built in the background.
An example use would be:
l = [0, 1, 2] for i, v in enumerate(iterrand(l)): print(f"{i:3}: {v:<5} {l}") if v < 4: l.append(randint(1, 9)) which might produce output like:
0: 2 [2, 1, 0] 1: 3 [2, 3, 0, 1] 2: 1 [2, 3, 1, 1, 0] 3: 0 [2, 3, 1, 0, 1, 3] 4: 1 [2, 3, 1, 0, 1, 3, 7] 5: 7 [2, 3, 1, 0, 1, 7, 7, 3] 6: 7 [2, 3, 1, 0, 1, 7, 7, 3] 7: 3 [2, 3, 1, 0, 1, 7, 7, 3] 8: 2 [2, 3, 1, 0, 1, 7, 7, 3, 2] 9: 3 [2, 3, 1, 0, 1, 7, 7, 3, 2, 3] 10: 2 [2, 3, 1, 0, 1, 7, 7, 3, 2, 3, 2] 11: 7 [2, 3, 1, 0, 1, 7, 7, 3, 2, 3, 2, 7]