Fisher-Yates 洗牌算法

Fisher-Yates 洗牌算法通过生成随机排列来对有限序列的元素进行洗牌。每个排列出现的可能性是均等的。该算法通过将序列的元素存储在一个袋子中，并从袋子中随机抽取每个元素来形成洗牌后的序列。

该算法以 Ronald Fisher 和 Frank Yates 的名字命名，他们设计了最初的洗牌方法，该算法是无偏的。它在相同条件下生成所有排列，因此获得的输出不受任何影响。然而，Fisher-Yates 算法的现代版本比原始版本更有效率。

Fisher-Yates 算法

原始方法

洗牌算法的原始方法涉及使用笔和纸来生成有限序列的随机排列。生成随机排列的算法如下：

步骤 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 交换后被移动到 D 的位置。

步骤 4

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

步骤 5

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

步骤 6

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

步骤 7

剩余的元素 C 保持不变，无需交换。

交换后获得的数组是最终的输出数组。

示例

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

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
// Function to perform Fisher-Yates Shuffle using the original method
void fisherYatesShuffle(char arr[], char n) {
    char output[n];  // Create an output array to store the shuffled elements
    char visited[n]; // Create a boolean array to keep track of visited elements
    // Initialize the visited array with zeros (false)
    for (char i = 0; i < n; i++) {
        visited[i] = 0;
    }
    // Perform the shuffle algorithm
    for (char i = 0; i < n; i++) {
        char j = rand() % n; // Generate a random index in the input array
        while (visited[j]) { // Find the next unvisited index
            j = rand() % n;
        }
        output[i] = arr[j]; // Add the element at the chosen index to the output array
        visited[j] = 1;     // Mark the element as visited
    }
    // Copy the shuffled elements back to the original array
    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)); // Seed the random number generator with the current time
    fisherYatesShuffle(arr, n); // Call the shuffle function
    printf("Shuffled array: ");
    for (char i = 0; i < n; i++) {
        printf("%c ", arr[i]); // Print the shuffled array
    }
    printf("\n");
    return 0;
}

Shuffled array: A B F D E C 

#include <iostream>
#include <vector>
#include <algorithm>
#include <random>
// Function to perform Fisher-Yates Shuffle using the original method
void fisherYatesShuffle(std::vector<char>& arr) {
    std::vector<char> output; // Create an output vector to store the shuffled elements
    std::vector<bool> visited(arr.size(), false); // Create a boolean vector to keep track of visited elements
    // Perform the shuffle algorithm
    for (char i = 0; i < arr.size(); i++) {
        char j = rand() % arr.size(); // Generate a random index in the input vector
        while (visited[j]) { // Find the next unvisited index
            j = rand() % arr.size();
        }
        output.push_back(arr[j]); // Add the element at the chosen index to the output vector
        visited[j] = true; // Mark the element as visited
    }
    arr = output; // Copy the shuffled elements back to the original vector
}
int main() {
    std::vector<char> arr = {'A', 'B', 'C', 'D', 'E', 'F'};
    srand(time(NULL)); // Seed the random number generator with the current time
    fisherYatesShuffle(arr); // Call the shuffle function
    std::cout << "Shuffled array: ";
    for (char c : arr) {
        std::cout << c << " "; // Print the shuffled array
    }
    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 {
    // Function to perform Fisher-Yates Shuffle using the original method
    public static List<Character> fisherYatesShuffle(List<Character> arr) {
        List<Character> output = new ArrayList<>(); // Create an output list to store the shuffled elements
        boolean[] visited = new boolean[arr.size()]; // Create a boolean array to keep track of visited elements
        // Perform the shuffle algorithms
        for (int i = 0; i < arr.size(); i++) {
            int j = new Random().nextInt(arr.size()); // Generate a random index in the input list
            while (visited[j]) { // Find the next unvisited index
                j = new Random().nextInt(arr.size());
            }
            output.add(arr.get(j)); // Add the element at the chosen index to the output list
            visited[j] = true; // Mark the element as visited
        }
        return output;
    }
    public static void main(String[] args) {
        List<Character> arr = List.of('A', 'B', 'C', 'D', 'E', 'F');
        Random rand = new Random(); // Seed the random number generator with the current time
        List<Character> shuffledArray = fisherYatesShuffle(arr); // Call the shuffle function
        System.out.print("Shuffled array: ");
        for (char c : shuffledArray) {
            System.out.print(c + " "); // Print the shuffled array
        }
        System.out.println();
    }
}

Shuffled array: D B E C A F 

import random
# Function to perform Fisher-Yates Shuffle using the original method
def fisherYatesShuffle(arr):
    output = []  # Create an output list to store the shuffled elements
    visited = [False] * len(
        arr)  # Create a boolean list to keep track of visited elements
    # Perform the shuffle algorithm
    for i in range(len(arr)):
        j = random.randint(0,
                           len(arr) -
                           1)  # Generate a random index in the input list
        while visited[j]:  # Find the next unvisited index
            j = random.randint(0, len(arr) - 1)
        output.append(
            arr[j])  # Add the element at the chosen index to the output list
        visited[j] = True  # Mark the element as visited
    return output
if __name__ == "__main__":
    arr = ['A', 'B', 'C', 'D', 'E', 'F']
    random.seed()  # Seed the random number generator with the current time
    shuffled_array = fisherYatesShuffle(arr)  # Call the shuffle function
    print("Shuffled array:", shuffled_array)  # Print the shuffled array

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