设计与分析 - Fisher-Yates Shuffle

Fisher-Yates 洗牌算法通过生成随机排列来洗牌有限的元素序列。每个排列发生的可能性是相同的。该算法的执行方式是将序列的元素存储在一个麻袋中，并从麻袋中随机抽取每个元素以形成打乱的序列。

该算法是在罗纳德·费舍尔（Ronald Fisher）和弗兰克·耶茨（Frank Yates）之后创造的，用于设计洗牌的原始方法，该算法是无偏的。它在相同的条件下生成所有排列，因此所实现的输出不会受到影响。然而，费舍尔-耶茨算法的现代版本比原始版本更有效。

费舍尔-耶茨算法

原始方法

Shuffle 算法的原始方法涉及笔和纸来生成有限序列的随机排列。生成随机排列的算法如下 -

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

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

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

步骤 4 - 进程终止后生成的输出列表是生成的随机排列。

现代算法

现代算法是原始 Fisher-Yates 洗牌算法的略微修改版本。修改的主要目标是通过降低原始方法的时间复杂度来计算机化原始算法。现代方法由理查德·德斯坦菲尔德 (Richard Durstenfeld) 开发，并由唐纳德·E·高德纳 (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]

原始方法示例

为了更好地描述该算法，让我们排列字母表前六个字母的给定有限序列。输入序列：ABCDE 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>
// 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']