ShuffleAnArray [source code]


public class ShuffleAnArray {
static
/******************************************************************************/
public class Solution {
    Random rd = new Random();
    int[] nums;

    public Solution(int[] nums) {
        if (nums.length > 0)
            this.nums = nums.clone();
    }

    /** Resets the array to its original configuration and return it. */
    public int[] reset() {
        if (nums == null)
            return new int[0];  //avoid return null
        else return nums;
    }

    /** Returns a random shuffling of the array. */
    public int[] shuffle() {
        if (nums == null)
            return new int[0];  //avoid return null
        int[] res = nums.clone();
        shuffle(res, 0);
        return res;
    }

    public void shuffle(int[] ar, int start) {
        if (start == ar.length - 1)
            return;
        int index = start + 1 + rd.nextInt(ar.length - start - 1);
        swap(ar, start, index);
        shuffle(ar, start + 1);
    }

    public void swap(int[] ar, int i, int j) {
        int temp = ar[j];
        ar[j] = ar[i];
        ar[i] = temp;
    }
}
/******************************************************************************/

    public static void main(String[] args) {
        // ShuffleAnArray.Solution tester = new ShuffleAnArray.Solution();
    }
}

回顾一下random的用法:

nextInt(int bound): Returns a pseudorandom, uniformly distributed int value between 0 (inclusive) and the specified value (exclusive), drawn from this random number generator's sequence.

至于shuffle本身的做法好像以前是学过的, 就是一个swap, shuffle, swap的recursion就行了;

另外这里的好像第二个swap不需要? 因为我们只要一个permutation, 而不是所有的, 所以不需要像backtracking的时候那样, recursive call上行退出的时候还要undo;

另外这个算法其实也可以帮助理解shuffle/permutation的本质: 我们说一个recursion算法, 除去recursive call和base case的部分往往就是算法的主心骨内容, 实质性的操作; 所以permute这个东西本质其实就是swap;

另外读题的时候"equally likely"这个看到的时候也不用太慌, 其实就是常见的random的意思; 编程毕竟不是纯数学, 有些看起来有一千种理解方式的词句, 其实真正在编程问题当中能让你联想到的就那么几个东西;

return empty rather than null

这个题目还有一个教训, 就是avoid return null. 这个之前discussion里面也看到人说过; 这个题目的OJ就正好也对这个做出了判断; 如果真的是Null的情形, 应该自己return一个类似new int[0]这样的Empty而不是Null;

另外我一开始的做法就是object里面保存一个copy, 然后每次被call shuffle的时候, 直接从最开始的原状来一次random的shuffle; 但是这样好像最后得到的结果不对; 说明这里OJ对于equally likely的要求是绝对的, 而不是概率上的. 那么就要想别的办法了; //并不是这样, 你自己算法一开始就写的不对, probabilistically;

最后好不容易调出来bug了(见下面), 最后的速度是257ms (58%), 可以接受;

这个是discussion最优解:

public class Solution {  
    private int[] nums;  
    private Random random;  

    public Solution(int[] nums) {  
        this.nums = nums;  
        random = new Random();  
    }  

    public int[] reset() {  
        return nums;  
    }  

    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);  
        // }  
        // for (int j = a.length - 1; j > 0; j--) {  
        //     int i = random.nextInt(j + 1);  
        //     swap(a, i, j);  
        // }  
        for (int j = 0; j < a.length - 1; j++) {  
            // int i = j + 1 + random.nextInt(nums.length - j - 1);  
            int i = j + random.nextInt(nums.length - j);  
            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;  
    }  
}

注意看这里的三个循环:

for(int j = 1; j < a.length; j++) {  
    int i = random.nextInt(j + 1);  
    swap(a, i, j);  
}  
for (int j = a.length - 1; j > 0; j--) {  
    int i = random.nextInt(j + 1);  
    swap(a, i, j);  
}  
for (int j = 0; j < a.length - 1; j++) {  
    // int i = j + 1 + random.nextInt(nums.length - j - 1);  
    int i = j + random.nextInt(nums.length - j);  
    swap(a, i, j);  
}

这三个循环其实是达到同样的目的的; 第一个循环是一个正序的做法, 后面两个循环是一个倒序的做法, 其中第三个循环跟我自己的recursion的做法是等价的;

这道题刚开始很长时间一个bug没有调出来(有一个大case过不了); 当时就是因为用了类似loop3里面被comment那一句的逻辑. 具体来说, 比如有index从0到3, 长度为4的一个array, 我一开始错误的做法是, 先是swap(0, (random within 1..3)).

首先我们先来思考一下这种倒序shuffle的正确性如何证明, 也就是背后实际上干的是什么? 这个其实之前有道题目的时候已经总结过了, 倒序shuffle其实就等价于assign value (chosen randomly) to index consecutively. 如果是loop3, 那么其实实际上的操作内容就是从0到2(也可以认为到3), 给entry选定value(by swapping). 如果是loop2, 就是从3到0;

那么我之前swap(0, (random within 1..3))的做法的错误之处在于, 这样做了之后, 最开始的[0]的这个value, 就永远不可能出现在[0]的位置! 也就是最后得到的array在[0]的位置, 是1..3(对应的值)当中等概率的一个, 但是这不是我们要的, 我们要的是0..4对应的值当中等概率的任意一个;

另外, 随机赋值这种思路, 解释倒序shuffle确实没有问题, 但是解释正序好像有点说不通? 倒序的时候, 我们的一个invariant是, 在当前iteration被swap的这个index, 在后面的iteration就不会被影响(因为被exclude了, 下一个subproblem就不包含这个index了), 所以可以用一个类似assign的思路去理解; 但是如果是正序的做法, 好像这个invariant就没有了.

感觉可以大概用induction来证明一下: 首先思考一下这个正序循环的本质.

这个是discussion上面一个人对于正序循环的一个非常严谨的证明:

ps:

I choice to use 1-indexed rather that 0-indexed.

we designate P(i, j, k) to be the probability of the element originally at position i now is at position j when we finish swap process base on position k.

Proof: P(i, j, k) = 1 / k , 1 <= k <= n & 1 <= i , j <= k

first, we should notice that swap process based on position i won't affect elements after it, because we exchange it with an element before it.
k = 1, true, as we can only exchange it with itself, P(1, 1, 1) = 1 = 1 / 1

k = 2, true, as P(1,2,2) = P(1,1,1) = P(2,1,2) = P(2,2,2) = 1 / 2
Suppose P(i, j, m - 1) = 1 / (m - 1) holds for all i, j that 1 <= i, j <= m - 1. When k = m,
P(m, j, m) = 1 / m, because we randomly choice a new position in [1, m] for the element originally at position m
for any element originally at postion i that i is [1, m - 1],
j = m, P(i, m, m) = sum ( P(i, a, m - 1) 1 / m ), a = 1, 2, ..., m - 1
                    = (1 / (m - 1) * 1 / m  + 1 / (m - 1) * 1 / m + ..... + 1 / (m - 1) * 1 / m)   
                = (m - 1) * ( 1 / (m - 1) * 1 / m)  
                = 1 / m*  
above formula means: the element originally at position i is at position a when finishing swap based on position (m - 1), and now we choice to swap it with element at position m. a has (m - 1) possible values.
j != m, then this element is not chose, so it is not affected in this turn. If it at position j, it must be at position j last turn.
P(i, j, m) = P(i, j, m - 1) (m -1) / m = 1 / (m - 1) (m - 1) / m = 1/ m
proved!

这个证明十分的严谨. 需要学习的主要就是他对于这个P, 概率的定义(或者说事件的定义). 这个我在想自己的证明的时候就没有想到, 事实上, 我根本就没有往这个概率probability of what at what的思路上去想, 我的想法还是集中在permutation本身的理解上面;

另外这个人的证明本身的时候, 也是层层推进, 而且分情况讨论非常清晰;

在理解这个解法的同时, 我意识到我对倒序的理解其实不够充分; 比如总长度是n, 0的位置是[0]..[n-1]当中的随机一个这个是正确的, 但是[1]的则是[1]..[n-1]当中的随机一个, 这个跟证明1/n的概率之间其实还是缺少一个转化的; 后面想了一下, 实际上倒序的情况还是要用induction来证明; 我感觉我之前的想法更多的还是类似于: 比如我们有1..n这么多的value, 放在一个箱子里, 然后一个一个的抽, 抽到第一个放在0位置, 然后第二个放在1位置, 这样最后得到的就是一个随机permutation;

另外这个算法其实是有一个正经的名字的, 叫Fisher Yates Algorithm. 也有说这个算法叫Knuth Shuffle;

这个是另外一个人的写法:

public class Solution {  

    private int[] nums;  

    public Solution(int[] nums) {  
        this.nums = nums;  
    }  

    public int[] reset() {  
        return nums;  
    }  

    public int[] shuffle() {  
        int[] rand = new int[nums.length];  
        for (int i = 0; i < nums.length; i++){  
            int r = (int) (Math.random() * (i+1));  
            rand[i] = rand[r];  
            rand[r] = nums[i];  
        }  
        return rand;  
    }  
}

虽然本质是一样的, 但是写法简短很多, 而且没有一个explicit的swap; 同样的, 注意这里random的上限同样是i + 1 for i. 大概看准的一点就是其实不需要专门先缓存[i], 因为[i]这个边缘位置在每一个iteration都是第一次被swap, 所以rand[i]其实就等于nums[i]. 这个问题为了实现reset要专门维护一个original copy, 这里这个做法反而把这个original copy派上了额外的用场;

discussion里面大部分的做法都是iteration的做法, 不过我个人来说还是更加喜欢recursion的做法;

关于这个avoid return null的观点, Stefan貌似很不认同. 不过我最后也没有去跟他吵这个. 我个人还是认为应该支持这个观点, 另外, 很多其他的观点, 一个比较好的避免return null的办法就是自己不要明确的写return null这样的语句就行了; 只要你自己不写, 并且别人给你constructor的argument不是Null, 也就是别人不pass null, 那么你自己的代码里面只要不写explicit的return null: 而是转过来使用类似return Arrays.copyOf(nums, nums.length);等操作就行了; 而且大部分只要你不是先无参的constructor, 那么最后就可以保证最后你的instance var不是Null(as long you have an instance of this object), 最后也就不用担心会return null;

Problem Description

Shuffle a set of numbers without duplicates.

Example:

// Init an array with set 1, 2, and 3.  
int[] nums = {1,2,3};  
Solution solution = new Solution(nums);  

// Shuffle the array [1,2,3] and return its result. Any permutation of [1,2,3] must equally likely to be returned.  
solution.shuffle();  

// Resets the array back to its original configuration [1,2,3].  
solution.reset();  

// Returns the random shuffling of array [1,2,3].  
solution.shuffle();

Difficulty:Medium
Total Accepted:28.1K
Total Submissions:60.5K
Contributor: LeetCode

/**

Your Solution object will be instantiated and called as such:
Solution obj = new Solution(nums);
int[] param_1 = obj.reset();
int[] param_2 = obj.shuffle();
*/

Problem Description

这个是我在discussion发的帖子, 主要是关于证明:

Caveats about Proof

I think the approach of proof for this problem should differ on how you write your code. There are two ways of doing so.
Increasing Order Loop

for(int j = 1; j < a.length; j++) {  
    int i = random.nextInt(j + 1);  
    swap(a, i, j);  
}

Decreasing Order Loop

for (int j = a.length - 1; j > 0; j--) {  
    int i = random.nextInt(j + 1);  
    swap(a, i, j);  
}  
for (int j = 0; j < a.length - 1; j++) {  
    int i = j + random.nextInt(nums.length - j);  
    swap(a, i, j);  
}

Note that these two decreasing order loop does the same job for this problem. But when it comes to proof of correctness for these two kinds of loops, the approach is quite different.

Definition

First, let me explain the phrasing of increasing and decreasing. In increasing order loop, then range of swapping increases by iteration. In decreasing** order loop though, the range of swapping* decreases. Verify for yourself for the above code.

Decreasing Order Loop

For decreasing order loop: this loop does a simple job, it assigns one value to one index at one iteration. For example, if we have 0,1,2,3,4 as indices, we do:

swap [0] with a random from [0]..[4]: this iteration assigns [0].
swap [1] with a random from [1]..[4]: this iteration assigns [1].
swap [2] with a random from [2]..[4]: this iteration assigns [2].
...

By assigning*, we can see that each iteration assigns one entry definitely, and this entry will never be modified in future iterations.

I hereby provide an informal and non-mathmatical proof:
First, I claim that a shuffled array where each entry is equally likely to appear in each index, is just another way of saying picking a uniformly random permutation. This may require some proof per se, but let's take it as is for now.
Second, think about what the above iteration-by-iteration assigning is doing actually: you have a box of numbers, from the original nums array, all the entries. In iteration 1, you pick one number, and you put it on position [0], note that you did not put this number back to the box. In iteration 2, you pick another, and put to [1], also not putting it back...What is this? Isn't this just the process of permutation? And since each picking is uniformly random, the final permutation is also uniformly random.

Of course, this is not a formal proof. You can also try to prove it as in an Increasing Order loop's case.

Increasing Order Loop

That is what is written here. I thought for a while for an intuitive way to relate to this loop to no avail. It seems like an induction on probability mathematical approach can not be avoided in this situation.

I particularly like this proof:
@Andrewli said in First Accepted Solution - Java:

@kaiqi I think another entrance could make the induction more tractable and convincing.
ps:

I choice to use 1-indexed rather that 0-indexed.

we designate P(i, j, k) to be the probability of the element originally at position i now is at position j when we finish swap process base on position k.

Proof: P(i, j, k) = 1 / k , 1 <= k <= n & 1 <= i , j <= k

first, we should notice that swap process based on position i won't affect elements after it, because we exchange it with an element before it.
k = 1, true, as we can only exchange it with itself, P(1, 1, 1) = 1 = 1 / 1

k = 2, true, as P(1,2,2) = P(1,1,1) = P(2,1,2) = P(2,2,2) = 1 / 2
Suppose P(i, j, m - 1) = 1 / (m - 1) holds for all i, j that 1 <= i, j <= m - 1. When k = m,
P(m, j, m) = 1 / m, because we randomly choice a new position in [1, m] for the element originally at position m
for any element originally at postion i that i is [1, m - 1],
j = m, P(i, m, m) = sum ( P(i, a, m - 1) 1 / m ), a = 1, 2, ..., m - 1
                    = (1 / (m - 1) * 1 / m  + 1 / (m - 1) * 1 / m + ..... + 1 / (m - 1) * 1 / m)   
                = (m - 1) * ( 1 / (m - 1) * 1 / m)  
                = 1 / m*  
above formula means: the element originally at position i is at position a when finishing swap based on position (m - 1), and now we choice to swap it with element at position m. a has (m - 1) possible values.
j != m, then this element is not chose, so it is not affected in this turn. If it at position j, it must be at position j last turn.
P(i, j, m) = P(i, j, m - 1) (m -1) / m = 1 / (m - 1) (m - 1) / m = 1/ m
proved!

Just A Little Thing

I personally does not like returning null in this problem. I am mentioning this because I saw a lot of people doing this while browsing the solutions.

This is something I saw earlier and I quite agree.
@soumyadeep2007 said in Don't return null for functions returning collections/iterables:

Usually when a method returns a collection and the method has no result to return, we have two options:

Return null: This results in breakage of client code if it doesn't check for that null.
public List<Order> getOrders() {  
  //..  
}  
.  
.  
List<Order> orders = getOrders();  
for(Order order : orders) { //NullPointerException here if getOrders returned null!  
  System.out.println(order);  
}
So the client will be forced to write:
if(orders != null) { //guard  
  for(Order order : orders) { //NullPointerException here if getOrders returned null!  
      System.out.println(order);  
  }  
}
Return an empty list: Client code will not break and no need to introduce a guard! Much cleaner code! So the below code will suffice:
List<Order> orders = getOrders();  
for(Order order : orders) {  
  System.out.println(order);  
}
EDIT : ~~Best way to return an empty list is to return one that is immutable by returningCollections.emptyList() from the concerned function.~~

Note: The above example dealt with lists but you can extend this discussion to anything that is a Collection/Iterables.

LC384 ShuffleAnArray

ShuffleAnArray [source code]

return empty rather than null

Problem Description

Problem Description

Caveats about Proof

Definition

Decreasing Order Loop

Increasing Order Loop

Just A Little Thing

results matching ""

No results matching ""