Define another function to illustrate Reservoir Sampling

Documenting a few ideas about Reservoir Sampling while it's fresh on my mind.

1 files changed, 11 insertions, 0 deletions

diff --git a/scratch/facebook/hard/random-choice.py b/scratch/facebook/hard/random-choice.py
index 95e834a2eb01..a5c6e4e6ee81 100644
--- a/scratch/facebook/hard/random-choice.py
+++ b/scratch/facebook/hard/random-choice.py
@@ -26,6 +26,16 @@ def choose_b(m, xs):
     random.shuffle(ys)
     return ys[:m]
 
+def choose_c(m, xs):
+    """
+    This is one, possibly inefficient, way to randomly sample `m` elements from
+    `xs`.
+    """
+    choices = set()
+    while len(choices) < m:
+        choices.add(random.randint(0, len(xs) - 1))
+    return [xs[i] for i in choices]
+
 # ROYGBIV
 xs = [
     'red',
@@ -37,3 +47,4 @@ xs = [
     'violet',
 ]
 print(choose_b(3, xs))
+print(choose_c(3, xs))