Fisher–Yates shuffle是一种基于有限序列产生随机排列的算法。因为每次抽取每个元素都是等概率的，所以该算法产生一个无偏排列：每个排列的可能性相等。

# 1. Fisher–Yates shuffle原始算法

Fisher–Yates shuffle最开始描述在Ronald Fisher and Frank Yates的Statistical tables for biological, agricultural and medical research一书中。

1. 1到N的数字；
2. 从1到N之间随机抽取一个整数；
3. 从1到N的数字中删除第K个元素，并将其放置到结果中
4. 重复步骤2和3，直至元素耗尽
5. 结果中新的排列就是原来元素的随机排列

• 例子：

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 

# 原文：

Fisher–Yates shuffle

Shuffle a given array using Fisher–Yates shuffle Algorithm