Implement a class that shuffles a list of numbers so that every permutation is equally likely:
Solution(nums, rng):numsis a list of distinct ints;rngis arandom.Random. Use it for all randomness (e.g.rng.randrange(k)), never the globalrandommodule orrandom.shuffle.reset() -> list[int]: return the list in its original order.shuffle() -> list[int]: return a uniformly random permutation of the list.
Aim for O(n) per shuffle. A classic mistake is to walk the list and swap each position with a random position j picked from the whole range 0..n-1: that produces n^n equally likely swap sequences, which can't spread evenly over n! permutations, so some orders come up more often than others. The tests catch that.
Don't let a shuffle corrupt the original: reset() must still return it after any number of shuffles, and it must not be affected if the caller mutates a returned list.
s = Solution([5, 6, 7], random.Random(0))
s.shuffle() # e.g. [7, 5, 6], each of the 6 orders with probability 1/6
s.reset() # [5, 6, 7]
Constraints: 1 ≤ len(nums) ≤ 50.
Show hint
Build the shuffled list from the back: choose uniformly which of the remaining elements goes into the last unfilled position, then never touch that position again. Each step then has exactly as many choices as there are elements left.