随机排列与Fisher-Yates算法

目录

1. 随机排列

2. 均匀随机排列

3. Fisher-Yates Shuffle: Original Version

4. Fisher-Yates Shuffle: Modern Version

1. 随机排列

将上面7张牌进行随机排列，可能会得到下面结果。

2. 均匀随机排列

上面是集合  的均匀随机排列。

若一个集合含有  个元素，则共有  种排列。

• 从  种可能的序列中等概率随机选取一个。
• 某个元素出现在  个任意位置上的概率相等。
• 某个位置上为  个任意元素之一的概率相等。

3. Fisher-Yates Shuffle: Original Version

进行  轮循环，每轮循坏从原序列随机抽取一个元素，写入排列数组中，原序列中的空位由被抽取元素的后面元素都左移一位补平。

时间复杂度：

4. Fisher-Yates Shuffle: Modern Version

void permute(int arr[], int n){
for (int i=0; i<=n-2; i++){
// k从{0,1,…, n-i-1}中随机取样
int k = uniform(n-i);
// j的范围{i, i+1, …, n-1}
int j = i + k;
// 交换arr[i]和arr[j]
swap(arr[i],arr[j]);
}
}

第一轮循环中，随机抽取一个元素，与第一个元素交换，并且固定第一个元素。

第二轮循环中，把原来的第二个元素当作第一个元素，随机抽取一个元素，与第一个元素交换位置，并且固定第一个元素。

以此类推，第  轮循环中，把原来的第  个元素当作第一个元素，随机抽取一个元素，与第一个元素交换位置，并且固定第一个位置。

时间复杂度：