@@ -0,0 +1,1964 @@
+package com.freetymekiyan.algorithms.level.medium;%0A%0Aimport java.util.Random;%0A%0A/**%0A * Shuffle a set of numbers without duplicates.%0A * %3Cp%3E%0A * Example:%0A * %3Cp%3E%0A * // Init an array with set 1, 2, and 3.%0A * int%5B%5D nums = %7B1,2,3%7D;%0A * Solution solution = new Solution(nums);%0A * %3Cp%3E%0A * // Shuffle the array %5B1,2,3%5D and return its result. Any permutation of %5B1,2,3%5D must equally likely to be returned.%0A * solution.shuffle();%0A * %3Cp%3E%0A * // Resets the array back to its original configuration %5B1,2,3%5D.%0A * solution.reset();%0A * %3Cp%3E%0A * // Returns the r shuffling of array %5B1,2,3%5D.%0A * solution.shuffle();%0A */%0Apublic class ShuffleAnArray %7B%0A%0A    class Solution %7B%0A%0A        private final Random r;%0A        private int%5B%5D nums;%0A%0A        public Solution(int%5B%5D nums) %7B%0A            this.nums = nums;%0A            r = new Random();%0A        %7D%0A%0A        /** Resets the array to its original configuration and return it. */%0A        public int%5B%5D reset() %7B%0A            return nums;%0A        %7D%0A%0A        /**%0A         * Returns a r shuffling of the array.%0A         * Proof of probability:%0A         * Assume that all numbers from 0 to i have same probability of 1 / (1 + i).%0A         * If j = i, numbers won't change, so the probability  remains the same.%0A         * If j != i, a%5Bj%5D and a%5Bi%5D will swap.%0A         * Suppose x is the number in %5B0, i-1%5D that is going to swap with i.%0A         * The probability of this number shows at i is p(x at %5B0, i-1%5D) * p(i not in i)%0A         * (1 / i) * (1 - 1 / (i + 1)).%0A         */%0A        public int%5B%5D shuffle() %7B%0A            int%5B%5D a = nums.clone();%0A            for (int i = 1; i %3C a.length; i++) %7B%0A                int j = r.nextInt(i + 1);%0A                int temp = a%5Bi%5D;%0A                a%5Bi%5D = a%5Bj%5D;%0A                a%5Bj%5D = temp;%0A            %7D%0A            return a;%0A        %7D%0A    %7D%0A%0A/**%0A * Your Solution object will be instantiated and called as such:%0A * Solution obj = new Solution(nums);%0A * int%5B%5D param_1 = obj.reset();%0A * int%5B%5D param_2 = obj.shuffle();%0A */%0A%7D%0A

add Shuffle An Array