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();
這道題讓我們打亂一個(gè)數(shù)組，相當(dāng)于shuffle card problem。
我們可以用 Knuth-Durstenfeld Shuffle 洗牌算法 來解決這個(gè)問題
參考文章
- Knuth-Durstenfeld Shuffle
version1
class Solution {
Random rd;
int[] cards;
int[] nums;
public Solution(int[] nums) {
this.nums = nums;
this.cards = nums.clone();
this.rd = new Random();
}
/** Resets the array to its original configuration and return it. */
public int[] reset() {
this.cards = nums.clone();
return this.cards;
}
/** Returns a random shuffling of the array. */
public int[] shuffle() {
for (int i = 0; i < cards.length; i++) {
int remain = cards.length - i;
int rdIdx = rd.nextInt(remain);
int tmp = cards[i];
cards[i] = cards[i + rdIdx];
cards[i + rdIdx] = tmp;
}
return cards;
}
}
version2
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;
}
}
- 2.3 Inside-Out Algorithm
public class Solution {
private int[] nums;
public Solution(int[] nums) {
this.nums = nums;
}
/** 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() {
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;
}
}
Inside-Out Algorithm 算法的基本思思是從前向后掃描數(shù)據(jù)，在新數(shù)組中，位置r是前i個(gè)數(shù)中任意一個(gè)位置，把位置r的數(shù)據(jù)復(fù)制到位置i中，然后把新數(shù)組中位置r的數(shù)字替換為原數(shù)組位置i的數(shù)字。。
如果知道arr的lengh的話，可以改為for循環(huán)，由于是從前往后遍歷，所以可以應(yīng)對arr[]數(shù)目未知的情況，或者arr[]是一個(gè)動(dòng)態(tài)增加的情況。
https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle#The_%22inside-out%22_algorithm
證明：
原數(shù)組第i個(gè)數(shù)放倒前i個(gè)任意位置的概率為:
1/i * [i/(i + 1)] * [(i + 1) / (i + 1)] ...[(n - i)/n] = 1/n
我們當(dāng)index = i 的時(shí)候開始放置第i個(gè)位置的數(shù)， 放置到某個(gè)位置r的概率為1/i, index 再繼續(xù)往后便利的時(shí)候，我們不能再選中r的概率為 i / (i + 1), 然后可以以此類推。
原數(shù)組第i個(gè)數(shù)放倒i + 1 到 n 之間任意位置的概率是:
假設(shè)我們放到了第k個(gè)位置
此時(shí)rand(k) 等于i的概率為1/k, 并且遍歷到k之后不能把k這個(gè)位置的數(shù)給替換掉.
所以概率為 i / k * [k/(k + 1)] * [(k + 1) / (k + 2)] * ... * [(n - 1)/ n] = 1/n
所以總體來說，概率是1/n
