First Accepted Solution - Java


  • 47
    Q
    import java.util.Random;
    
    public class Solution {
        private int[] nums;
        private Random random;
    
        public Solution(int[] nums) {
            this.nums = nums;
            random = new Random();
        }
        
        /** Resets the array to its original configuration and return it. */
        public int[] reset() {
            return nums;
        }
        
        /** Returns a random shuffling of the array. */
        public int[] shuffle() {
            if(nums == null) return null;
            int[] a = nums.clone();
            for(int j = 1; j < a.length; j++) {
                int i = random.nextInt(j + 1);
                swap(a, i, j);
            }
            return a;
        }
        
        private void swap(int[] a, int i, int j) {
            int t = a[i];
            a[i] = a[j];
            a[j] = t;
        }
    }
    
    

  • 0
    C

    Why int i = random.nextInt(j + 1);, not int i = random.nextInt(j);?


  • 24
    Q

    nextInt(j + 1) returns a random num between [0, j]. By nextInt(j), you never get a chance to return the original order array.


  • 0
    C

    @qianzhige Got it. Thanks


  • 0
    X
    This post is deleted!

  • 0
    H

    @qianzhige Nice solution. Thanks!


  • 1
    X

    @xiangjun.song said in First Accepted Solution - Java:

    Why for(int j = 1; j < a.length; j++) ,j starts from 1
    Will it cause ArrayIndexOutOfBoundsException?


  • -2
    L
    This post is deleted!

  • 7
    W

    Didn't actually follow.
    Why

    int i = random.nextInt(j + 1);
    

    instead of

    int i = random.nextInt(sz);
    

  • 15
    D

    @Chengcheng.Pei It looks like we can give a little proof of correctness here. For the 0th element, the probability for that it stays at index 0 position, is 1/1 * (2-1)/2 * (3-1)/3 * ... (n-1)/n = 1/n. The probability for that it will stay at index 1 is 1/2 * (3-1)/3 * ... = 1/n. This means for the 0th element, it has 1/n probability to be placed into any position.

    Once we know that 0th element will stay at index x, for simplicity, we know that 0th element will stay at index 0, then what is the probability of 1st element to stay 1st position? it is 1/1 * 1/2 * ... (n-2)/(n-1) = 1/(n-1). This implies that for the 1st element, it has 1/(n-1) probability to be placed into any un-occupied position.

    Not quite sure whether we can do the above analysis by fixing 0th element's position.

    Then one complete sequence will have probability of 1/(n!) to be chosen, which fits the requirement.


  • 27
    K

    I saw some people asking why this algorithm is correct. Here is my understanding. Hope it helps.

    Proof: Suppose this algorithm works, i.e. for each position j (starting from 0), the probability of any number in the range[0,j] to be at position j is 1/(1+j).

    Let's look at int i = random.nextInt(j + 1):
    (1) If i == j, nums[j] does not need to change its position, which has probability 1/(1+j).
    (2) if i !=j, nums[j] needs to be swapped with nums[i]. The probability of any number x in the range [0,j-1] to be at position j = nums[j] changes its position * x is at position i
    = (1-1/(1+j)) * (1/j) = 1/(1+j)

    Each number has equal probability to be at any position.


  • 0
    M

    why do we need to generate a random int between (0..j+1)? why cant it be any integer less than the length of the array?
    Instead of random.nextInt(j + 1) why can't we just have random.nextInt(arr.length)?


  • 2
    A

    Thank all the posts above! Just to share another perspective and I hope it is interesting.

    Suppose that len(nums) = n.

    Algorithm:
    ○ for i in 0 ... n - 1: swap(nums[i], nums[random.randint(i, n - 1)]). # uniform sampling in the closed interval [i, n - 1]

    Proof:
    ○ To generate one sequence, there are n ways of generating the first number, n - 1 ways of generating the second number, n - 2 ways of generating the third number, ..., 1 way of generating the last number. Propability for any particular sequence is (1/n) * (1/(n - 1)) * (1/(n - 2)) * ... * 1/1 = 1/n!.
    ○ Any generated sequence must be of the same probability 1/n! In fact, we also know that there are n! possible sequences (permutations).

    Accepted implementation:

        def __init__(self, nums):
            self.nums = nums
            
        def reset(self):
            return self.nums
            
        def shuffle(self):
            shuffled = self.nums[:]
            n = len(shuffled)
            for i in range(n):
                swapIdx = random.randint(i, n - 1)
                shuffled[i], shuffled[swapIdx] = shuffled[swapIdx], shuffled[i]
            return shuffled
    

  • 2
    Y

    Geeksforgeeks has a detailed explanation here: http://www.geeksforgeeks.org/shuffle-a-given-array/
    Or for a more formal article: Fisher–Yates shuffle: https://en.wikipedia.org/wiki/Fisher–Yates_shuffle


  • 1
    C

    Here is my understanding of the correctness of this algorithm. Hope it will be helpful!

    Each element has equal probability of being at one of the available positions in the array.

    Iteration 1: 1 element , 1 available position.(i=0, j=0) Prob that this element is put in the available posiition is 1/1.

    Iteration 2: 2 elemenst, 2 available positions.
    prob that 0th element goes to 1st position (i=0, j=1)
    = Prob that 1st element doesnt remain in its original position * Prob that 0th element gets chosen out of all remaining elements to be in 1st position.
    = 1 - 1/2 * 1/1 = 1/2

    prob that 1st element goes to 1st position (i=1, j=1)
    = prob that 1st element remains in its original position * prob that none of the remaining elements get chosen.(as i = j)
    = 1/2 * 1 = 1/2

    Iteration 3: 3 elements, 3 available positions.
    prob that 0th element goes to 2nd position (i=0, j=2)
    = prob that 2nd element doesnt remain in its original position * prob that 0th element gets chosen out of all remaining elements to be in 2nd position
    = 1 - 1/3 * 1/2
    = 2/3 * 1/2
    = 1/3

    prob that 1st element goes to 2nd position (i=1, j=2)
    = prob that 2nd element doesnt remain in its original position * prob that 1st element gets chosen out of all remaining elements to be in 2nd position
    = 1 - 1/3 * 1/2
    = 2/3 * 1/2
    = 1/3

    prob that 2nd element goes to 2nd position (i=2, j=2)
    = prob that 2nd element remains in its original position * prob that none of the remaining elements get chosen.
    = 1/3 * 1 = 1/3

    Thus by choosing one element at random between [0, j+1) and swapping with jth element, we generate permutations with equal probability.

    We can generalize the above.


  • 0
    D

    nice solution ,thank you


  • 2

    shuffle() call doesn't really need a .clone() again.

    New array can be created from constructor just once.
    The subsequent shuffle calls can reuse the shuffled array, since shuffling a shuffled array will still be a legit shuffle.


  • 0

    @jaqenhgar we need to reset() it, so we have to keep a original copy.


  • 0

    @ellewoods You can have a copy of the original only once in the constructor. .. EDIT : as @StefanPochmann pointed out in the below post, you shouldn't.

    int[] input;
    int[] temp;
    public Solution(int[] nums) {
        input = nums;
        temp = Arrays.copyOf(nums, nums.length);
    }
    
    /** Resets the array to its original configuration and return it. */
    public int[] reset() {
        return input;
    }
    
    /** Returns a random shuffling of the array. */
    public int[] shuffle() {
        Random r = new Random();
        for(int i = 0; i < input.length; i++) {
            int randomIdx = i + r.nextInt(input.length - i);
            int swap = temp[randomIdx];
            temp[randomIdx] = temp[i];
            temp[i] = swap;
        }
        return temp;
    }

  • 1

    @jaqenhgar But then you're not doing what the problem statement tells you to do. And it tells you for good reason. For example, change your shuffling to this:

    public int[] shuffle() {
        if (temp.length < 2) return temp;
        Random r = new Random();
        int i = r.nextInt(input.length);
        int j = r.nextInt(input.length);
        int tmp = temp[i];
        temp[i] = temp[j];
        temp[j] = tmp;
        return temp;
    }
    

    Clearly that's wrong, swapping only two elements is no proper shuffling. But the judge can't help you detect the mistake. Because the re-"shuffling" of the already "shuffled" array fools the judge's statistics. The judge would point out the mistake if the instructions were followed.

    Also see my thread about this.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.