Floyd's Sampling Algorithm
5 days ago
- #Floyd's algorithm
- #sampling algorithms
- #random subsets
- Floyd's sampling algorithm generates a uniformly random subset of size k from {1, 2, ..., n} using a set and a loop from n - k + 1 to n.
- The algorithm works by deciding for each iteration whether to add a random number t or the current index i to the set, ensuring no duplicates.
- A key intuition is that each step transforms a uniform k-subset of [1..n] into a uniform (k+1)-subset of [1..n+1] via a k+1-to-1 mapping.
- An alternative perspective connects Floyd's algorithm to the Fisher-Yates shuffle, where it corresponds to the last k swaps, directly producing a random sample.
- The algorithm is praised for its elegance and has practical implementations in code, often noted for being 'cool' or magical due to its non-intuitive branch logic.