Fisher-Yates 打乱算法

Fisher-Yates 打乱算法通过生成随机排列来打乱有限元素序列。每个排列发生的可能性均等。该算法的执行过程是：将序列中的元素存储在一个"麻袋"中，然后从中随机抽取每个元素，形成打乱后的序列。

该算法以 Ronald Fisher 和 Frank Yates 的名字命名，以纪念他们设计了最初的打乱方法，具有无偏性。它在相同条件下生成所有排列，因此输出结果不受影响。然而，现代版本的 Fisher-Yates 算法比原始版本更高效。

Fisher-Yates 算法

原始方法

Shuffle 算法的原始方法需要用纸笔对有限序列进行随机排列。生成随机排列的算法如下：−

步骤 1 − 写下有限序列中的所有元素。声明一个单独的列表来存储获得的输出。

步骤 2 − 在输入序列中随机选择一个元素 i 并将其添加到输出列表中。将元素 i 标记为已访问。

步骤 3 −重复步骤 2，直到有限序列中的所有元素都被访问并随机添加到输出列表中。

步骤 4 − 过程终止后生成的输出列表即为生成的随机排列。

现代算法

现代算法是对原始 Fisher-Yates 洗牌算法稍加修改的版本。修改的主要目标是通过降低原始方法的时间复杂度来实现原始算法的计算机化。现代方法由 Richard Durstenfeld 开发，并由 Donald E. Knuth 推广。

因此，现代方法使用交换而不是维护另一个输出列表来存储生成的随机排列。时间复杂度降低到 O(n) 而不是 O(n²)。算法如下 −

步骤 1 −写下有限序列中从 1 到 n 的元素。

步骤 2 − 在输入序列中随机选择一个元素 i，并将其与列表中最后一个未访问的元素交换。

步骤 3 − 重复步骤 2，直到有限序列中的所有元素都被访问并交换。

步骤 4 − 过程终止后生成的列表即为随机置换序列。

伪代码

在以下现代方法伪代码中，混洗是从数组的最高索引到最低索引进行的。

Fisher-Yates Shuffle (array of n elements):
for i from n−1 downto 1 do
   j ← random integer such that 0 ≤ j ≤ i
   exchange a[j] and a[i]

在以下现代方法伪代码中，从数组的最低索引到最高索引进行混洗。

Fisher-Yates Shuffle (array of n elements):
for i from 0 to n−2 do
   j ← random integer such that i ≤ j < n
   exchange a[i] and a[j]

原始方法示例

为了更好地描述该算法，我们对给定的字母表前六个字母的有限序列进行置换。输入序列：A B C D E F。

步骤 1

这称为纸笔法。我们考虑一个存储有限序列的输入数组和一个存储结果的输出数组。

步骤 2

随机选择任意元素，并在将其标记为已选中后将其添加到输出列表中。在本例中，我们选择元素 C。

步骤 3

下一个随机选择的元素是 E，它被标记并添加到输出列表中。

步骤 4

然后，随机函数选择下一个元素 A，并在将其标记为已访问后将其添加到输出数组中。

步骤 5

然后从中选择 F输入序列中剩余的元素，并在标记为已访问后添加到输出中。

步骤 6

下一个被选中添加到随机排列中的元素是 D。它被标记并添加到输出数组中。

步骤 7

输入列表中的最后一个元素是 B，因此它被标记并最终添加到输出列表中。

现代方法

为了降低原始方法的时间复杂度，引入了现代算法。现代方法使用交换来打乱序列——例如，该算法的工作原理类似于通过交换原始牌堆中牌的位置来洗牌。让我们通过一个例子来理解现代版 Fisher-Yates 算法的工作原理。

步骤 1

将字母表的前几个字母作为输入，并使用现代方法对其进行打乱。

步骤 2

随机选择元素 D，并将其与序列中最后一个未标记元素（在本例中为 F）交换。

步骤3

下一步，我们选择元素 B 与最后一个未标记元素"E"交换，因为 F 在上一步交换后已被移动到 D 的位置。

步骤 4

接下来，我们将元素 A 与 F 交换，因为它是列表中最后一个未标记元素。

步骤 5

然后将元素 F 与最后一个未标记元素 C 交换。

步骤 6

序列中剩余的元素最终可以交换，但由于随机函数选择了 E 作为元素，因此保留原样。

步骤 7

剩余元素 C 保持原样，不进行交换。

交换后得到的数组即为最终输出数组。

示例

以下是上述方法在各种编程语言中的实现 −

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
// 使用原始方法执行 Fisher-Yates Shuffle 的函数
void fisherYatesShuffle(char arr[], char n) {
    char output[n];  // 创建一个输出数组来存储打乱后的元素
    char visited[n]; // 创建一个布尔数组来跟踪访问过的元素
    // Initialize the visited array with zeros (false)
    for (char i = 0; i < n; i++) {
        visited[i] = 0;
    }
    // 执行 shuffle 算法
    for (char i = 0; i < n; i++) {
        char j = rand() % n; // 在输入数组中生成随机索引
        while (visited[j]) { // 查找下一个未访问的索引
            j = rand() % n;
        }
        output[i] = arr[j]; // 将所选索引处的元素添加到输出数组
        visited[j] = 1;     // 将元素标记为已访问
    }
    // 将打乱顺序的元素复制回原始数组
    for (char i = 0; i < n; i++) {
        arr[i] = output[i];
    }
}
int main() {
    char arr[] = {'A', 'B', 'C', 'D', 'E', 'F'};
    char n = sizeof(arr) / sizeof(arr[0]);

    srand(time(NULL)); // 使用当前时间为随机数生成器播种
    fisherYatesShuffle(arr, n); // 调用 shuffle 函数
    printf("Shuffled array: ");
    for (char i = 0; i < n; i++) {
        printf("%c ", arr[i]); // 打印打乱后的数组
    }
    printf("
");
    return 0;
}

Shuffled array: A B F D E C 

#include <iostream>
#include <vector>
#include <algorithm>
#include <random>
// 使用原始方法执行 Fisher-Yates Shuffle 的函数
void fisherYatesShuffle(std::vector<char>& arr) {
    std::vector<char> output; // 创建一个输出向量来存储混洗后的元素
    std::vector<bool> visited(arr.size(), false); // 创建一个布尔向量来跟踪访问过的元素
    // 执行 shuffle 算法
    for (char i = 0; i < arr.size(); i++) {
        char j = rand() % arr.size(); // 在输入向量中生成随机索引
        while (visited[j]) { // 查找下一个未访问的索引
            j = rand() % arr.size();
        }
        output.push_back(arr[j]); // 将所选索引处的元素添加到输出向量
        visited[j] = true; // 将元素标记为已访问
    }
    arr = output; // 将打乱的元素复制回原始向量
}
int main() {
    std::vector<char> arr = {'A', 'B', 'C', 'D', 'E', 'F'};
    srand(time(NULL)); // 使用当前时间为随机数生成器播种
    fisherYatesShuffle(arr); // 调用 shuffle 函数
    std::cout << "Shuffled array: ";
    for (char c : arr) {
        std::cout << c << " "; // 打印打乱后的数组
    }
    std::cout << std::endl;
    return 0;
}

Shuffled array: D B A F C E

import java.util.ArrayList;
import java.util.List;
import java.util.Random;
public class FisherYatesShuffle {
    // 使用原始方法执行 Fisher-Yates Shuffle 的函数
    public static List<Character> fisherYatesShuffle(List<Character> arr) {
        List<Character> output = new ArrayList<>(); // 创建输出列表来存储打乱后的元素
        boolean[] visited = new boolean[arr.size()]; // 创建一个布尔数组来跟踪访问过的元素
        // 执行 shuffle 算法s
        for (int i = 0; i < arr.size(); i++) {
            int j = new Random().nextInt(arr.size()); // 在输入列表中生成随机索引
            while (visited[j]) { // 查找下一个未访问的索引
                j = new Random().nextInt(arr.size());
            }
            output.add(arr.get(j)); // 将所选索引处的元素添加到输出列表
            visited[j] = true; // 将元素标记为已访问
        }
        return output;
    }
    public static void main(String[] args) {
        List<Character> arr = List.of('A', 'B', 'C', 'D', 'E', 'F');
        Random rand = new Random(); // 使用当前时间为随机数生成器播种
        List<Character> shuffledArray = fisherYatesShuffle(arr); // 调用 shuffle 函数
        System.out.print("Shuffled array: ");
        for (char c : shuffledArray) {
            System.out.print(c + " "); // 打印打乱后的数组
        }
        System.out.println();
    }
}

Shuffled array: D B E C A F 

import random
# 使用原始方法执行 Fisher-Yates Shuffle 的函数
def fisherYatesShuffle(arr):
    output = []  # 创建输出列表来存储打乱后的元素
    visited = [False] * len(
        arr)  # 创建一个布尔列表来跟踪访问过的元素
    # 执行 shuffle 算法
    for i in range(len(arr)):
        j = random.randint(0,
                           len(arr) -
                           1)  # 在输入列表中生成随机索引
        while visited[j]:  # 查找下一个未访问的索引
            j = random.randint(0, len(arr) - 1)
        output.append(
            arr[j])  # 将所选索引处的元素添加到输出列表
        visited[j] = True  # 将元素标记为已访问
    return output
if __name__ == "__main__":
    arr = ['A', 'B', 'C', 'D', 'E', 'F']
    random.seed()  # 使用当前时间为随机数生成器播种
    shuffled_array = fisherYatesShuffle(arr)  # 调用 shuffle 函数
    print("Shuffled array:", shuffled_array)  # 打印打乱后的数组

Shuffled array: ['D', 'C', 'A', 'B', 'F', 'E']