Fisher–Yates shuffle是一种基于有限序列产生随机排列的算法。因为每次抽取每个元素都是等概率的，所以该算法产生一个无偏排列：每个排列的可能性相等。
# 1. Fisher–Yates shuffle原始算法
Fisher–Yates shuffle最开始描述在Ronald Fisher and Frank Yates的Statistical tables for biological, agricultural and medical research一书中。
- 1到N的数字；
- 从1到N之间随机抽取一个整数；
- 从1到N的数字中删除第K个元素，并将其放置到结果中
- 重复步骤2和3，直至元素耗尽
- 结果中新的排列就是原来元素的随机排列
- 例子：
A到H的排列
image.png
抽取1-8之间的随机数
保存对应位置的元素到结果，并删除原始排列中的元素
image.png
image.png
image.png
# 2. Fisher–Yates shuffle现代算法
原始方法会花费不必要的时间来计算上面第3步中剩余的数字；新方法做出改进，就是将挑选的元素和最后一个元素进行互换。
-- To shuffle an array a of n elements (indices 0..n-1):
for i from n−1 downto 1 do
j ← random integer such that 0 ≤ j ≤ i
exchange a[j] and a[i]
相反方向的排列
-- To shuffle an array a of n elements (indices 0..n-1):
for i from 0 to n−2 do
j ← random integer such that i ≤ j < n
exchange a[i] and a[j]
- 例子：
A到H的排列
image.png
抽取1-8之间的随机数
保存对应位置的元素到结果，并删除原始排列中的元素
image.png
image.png
image.png
# 3. 实现
#include <stdlib.h>
#include <time.h>
#include <vector>
#include <iostream>
#include <numeric>
using namespace std;
void swap (int *a, int *b)
{
int temp = *a;
*a = *b;
*b = temp;
}
void printArray (int arr[], int n)
{
for (int i = 0; i < n; i++)
cout << arr[i] << " ";
cout << "\n";
}
void randomize (int arr[], int n)
{
unsigned int seed =1;
srand (seed);
for (int i = n - 1; i >= 0; i--)
{
int j = rand() % (i + 1);
swap(&arr[i], &arr[j]);
}
}
int main()
{
int arr[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
int n = sizeof(arr) / sizeof(arr[0]);
printArray(arr, n);
randomize (arr, n);
printArray(arr, n);
return 0;
}
//0 1 2 3 4 5 6 7 8 9
//9 8 4 2 0 6 5 1 7 3
#include <stdlib.h>
#include <time.h>
#include <vector>
#include <iostream>
#include <numeric>
using namespace std;
void printFun(std::vector<int> vec)
{
for (int i = 0; i < vec.size(); i++)
{cout << vec[i] << " ";}
cout << "\n";
}
std::vector<int> randomize (int range, int n, unsigned int seed)
{
//定义feature index
std::vector<int> vec(range);
std::iota(vec.begin(), vec.end(), 0);
srand (seed);
std::vector<int> vec2;
int len = vec.size()-1;
for (int i = n; i > 0; i--)
{
int j = rand() % (len+1);
vec2.push_back(vec[j]);
std::swap(vec[j], vec[len]);
len = len-1;
}
return vec2;
}
int main()
{
std::vector<int> vec(11);
std::iota(vec.begin(), vec.end(), 0);
printFun(vec);
std::vector<int> vec2 = randomize (vec.size(),11,1);
printFun(vec2);
return 0;
}
//0 1 2 3 4 5 6 7 8 9 10
//6 10 0 3 1 9 5 8 7 4 2
# 原文：
网友评论