Fisher-Yates Shuffle

# Fisher-Yates Shuffle ## Difficulty Medium ## Tags `array`, `randomization` ## Problem Statement Write a function to shuffle an array of integers such that every permutation is equally likely (uniform distribution). The shuffle must be performed **in-place**. ## Constraints - 1 ≤ nums.length ≤ 200 - -10⁶ ≤ nums[i] ≤ 10⁶ - Time complexity: O(n) - Space complexity: O(1) ## Signatures ### Python ```python def shuffle(nums: List[int]) -> None: pass ``` ### Java ```java public class Solution { public void shuffle(List<Integer> nums) { return null; } } ``` ### Csharp ```csharp public class Solution { public void shuffle(IList<int> nums) { throw new NotImplementedException(); } } ``` ### Cpp ```cpp class Solution { public: void shuffle(vector<int> nums) { } }; ``` ### C ```c void shuffle(int* nums) { } ``` ### Ruby ```ruby def shuffle(nums) end ``` ### Perl ```perl sub shuffle { my ($self, @args) = @_; } ``` ### Scala ```scala object Solution { def shuffle(nums: List[Int]): Unit = { } } ``` ### Haskell ```haskell shuffle :: ... -> ... shuffle args = undefined ``` ### Clojure ```clojure (defn shuffle [nums] ) ``` ### Scheme ```scheme (define (shuffle nums) ) ``` ## Examples ### Example 1 **Input:** ``` nums = [1, 2, 3, 4, 5] ``` **Output:** ``` [3, 1, 5, 2, 4] # One of 120 possible permutations ``` **Explanation:** Each of the 5! = 120 permutations has probability 1/120. ### Example 2 **Input:** ``` nums = [1, 2] ``` **Output:** ``` [2, 1] or [1, 2] # Each with probability 1/2 ``` ## Hints 1. Use the Fisher-Yates (also known as Knuth) shuffle algorithm. 2. Iterate from the last element to the first (or first to last). 3. For each position i, pick a random index j from [0, i] (inclusive). 4. Swap elements at positions i and j. ### Algorithm (Modern Version) ``` for i from n-1 down to 1: j = random integer in [0, i] swap nums[i] and nums[j] ``` This guarantees each permutation has equal probability.