# Prove an Incremental Shuffle Is Uniform Consider this in-place shuffle for an array of length `n`: ```text for i from 0 through n - 1: j = a uniformly random integer in [0, i] swap(array[i], array[j]) ``` Explain what the function does and prove by induction that, assuming independent uniform random choices, every permutation of distinct input elements has probability exactly `1 / n!`. ### Constraints & Assumptions - The random range includes both endpoints. - Random choices at different iterations are independent and unbiased. - Treat input elements as distinct for the proof. - The implementation mutates the input array and uses constant auxiliary space. ### Clarifying Questions to Ask - Is the random-number API's upper endpoint inclusive or exclusive? - Is the task asking for a proof of permutation uniformity or only uniform marginal positions? - May the input contain equal values, and if so are occurrences considered distinguishable? - Are cryptographic unpredictability and reproducibility relevant, or only mathematical fairness? ### What a Strong Answer Covers - Recognition as the forward form of the Fisher-Yates shuffle. - A precise induction invariant over the first `i + 1` positions. - Why each prior permutation and final location of the new element correspond to one outcome. - The probability calculation `1 / i! * 1 / (i + 1) = 1 / (i + 1)!`. - Random-range off-by-one errors and modulo-biased random-number generation. ### Follow-up Questions - Does proving every element has a uniform final position prove every permutation is uniform? - What changes when equal values are observationally indistinguishable? - How would a bad `random() % (i + 1)` implementation introduce bias? - How can you make a test reproducible without changing the production algorithm?