Shuffle

• Shuffle
  • Fisher–Yates shuffle
  • Easy Proof
  • Reference

Fisher–Yates shuffle

  public int[] shuffle() {
    /*
     * Using Fisher and Yates Algorithm
     * Proof: https://cs.stackexchange.com/questions/2152/how-to-prove-correctness-of-a-shuffle-algorithm?utm_medium=organic&utm_source=google_rich_qa&utm_campaign=google_rich_qa
     */
    final int[] res = new int[nums.length];
    System.arraycopy(nums, 0, res, 0, nums.length);
    for (int i = 1; i < nums.length; i++) {
      final int swapIndex = random.nextInt(i + 1);
      swap(res, swapIndex, i);
    }
    return res;
  }

Easy Proof

数学归纳法

1. base case 显然成立
2. 假设 n = k 结论成立
3. 当 n = k + 1 时，
   1. k + 1出现在任意位置上都是 1/(k + 1).
   2. 假设 j ∈ [1, k] 的出现在 [1, k] 的概率都是 1/k; When loop to k + 1, there is 1/(k + 1) to be picked from the current position. Mapping to all, the probability of j shows up in [1, k], but eventually on k + 1, will be k / (k + 1) * (1 / k) = 1 / (1 + k)

Reference

Fisher–Yates shuffle