Find centralized, trusted content and collaborate around the technologies you use most.
Learn more about CollectivesStack Internal
Knowledge at work
Bring the best of human thought and AI automation together at your work.
Explore Stack InternalUpdate: To test correctness, I'd do something like:
# trivial tests assert list(iterrand([])) == [] assert list(iterrand([1])) == [1] # bigger uniformity test from collections import Counter # tally 1M draws c = Counter() for _ in range(10**6): c[tuple(iterrand([1, 2, 3, 4, 5]))] += 1 # ensure it's uniform assert all(7945 < v < 8728 for v in c.values()) # above constants calculated in R via: # k<-120;p<-0.001/k;qbinom(c(p,1-p), 1e6, 1/k)) Update: To test correctness, I'd do something like:
# trivial tests assert list(iterrand([])) == [] assert list(iterrand([1])) == [1] # bigger uniformity test from collections import Counter # tally 1M draws c = Counter() for _ in range(10**6): c[tuple(iterrand([1, 2, 3, 4, 5]))] += 1 # ensure it's uniform assert all(7945 < v < 8728 for v in c.values()) # above constants calculated in R via: # k<-120;p<-0.001/k;qbinom(c(p,1-p), 1e6, 1/k)) 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]