3.1 随机排列

Random Permutation（随机排列）

What is uniform random permutation?

Fisher-Yates 洗牌算法

排列数等于n!

“uniform random permutation”（均匀随机排列）是指生成一个排列，其中每个可能的排列都以相等的概率出现。具体来说，对于含有n个元素的集合，它的所有n!个排列中的每一个都有相同的概率被选中。

实现均匀随机排列的一种简单方法是 Fisher-Yates 洗牌算法。该算法基于迭代，从最后一个元素开始，每次随机选择当前位置及之前的一个位置，并将它们的元素交换。通过不断重复这个过程，最终得到一个均匀随机排列。

这种排列方法在各种应用中都很有用，例如在随机化算法、模拟实验和密码学中。在实际应用中，均匀随机排列通常要求具有良好的随机性质，以确保生成的排列满足统计学上的随机性要求。

Fisher-Yates Shuffle

Fisher-Yates Shuffle，又称为洗牌算法，是一种用于随机排列数组元素的有效且简单的算法。其目标是生成一个均匀随机的排列，即每个元素在排列中出现的概率相等。下面是Fisher-Yates Shuffle的详细步骤：

1. 初始化： 算法开始时，数组中的元素按照其原始顺序排列。
2. 迭代： 从数组的最后一个元素开始，依次向前迭代到第一个元素。
3. 随机选择： 对于当前迭代的位置（假设为i），生成一个[0, i]范围内的随机整数 j。
4. 交换元素： 将当前位置（i）的元素与随机选择位置（j）的元素进行交换。
5. 递减迭代： 继续迭代，减小当前位置，直到第一个元素。

通过这个过程，每个元素都有机会被选择到任何一个位置，而且每个位置被选择的概率是相等的。因此，经过足够的迭代次数后，数组中的元素将被洗牌成一个均匀随机的排列。

Fisher-Yates Shuffle是一种简单而强大的洗牌算法，广泛应用于计算机科学领域，尤其在实现随机算法、模拟实验和游戏开发等方面。

以下是使用Python实现Fisher-Yates Shuffle的简单代码：

import random

def fisher_yates_shuffle(arr):
    # 从最后一个元素开始迭代
    for i in range(len(arr) - 1, 0, -1):
        # 生成随机索引，范围是 [0, i]
        j = random.randint(0, i)

        # 交换当前位置的元素与随机选择位置的元素
        arr[i], arr[j] = arr[j], arr[i]

# 示例用法
my_array = [1, 2, 3, 4, 5]
fisher_yates_shuffle(my_array)
print(my_array)

这段代码使用了Python的 random 模块中的 randint 函数来生成随机整数。通过调用 fisher_yates_shuffle 函数，可以对任意数组进行Fisher-Yates Shuffle。在示例用法中，数组 [1, 2, 3, 4, 5] 被洗牌，打印结果可能是类似 [3, 5, 1, 4, 2] 的随机排列。

range(len(arr) - 1, 0, -1) 是一个用于生成迭代索引的 Python 内置函数 range 的调用。具体来说，这个函数的参数是起始值、结束值和步长。

• len(arr) - 1: 这是起始值，表示从数组的最后一个元素开始。
• 0: 这是结束值（不包含在范围内），表示索引递减至 0。
• -1: 这是步长，表示递减的步长为 1。

因此， range(len(arr) - 1, 0, -1) 生成了一个逆序的索引序列，从数组的最后一个元素开始递减到第一个元素。这个逆序的索引序列用于在 Fisher-Yates Shuffle 算法中迭代数组的位置。在每次迭代中，会随机选择一个之前的位置，并与当前位置的元素交换，从而完成洗牌的过程。

Fisher-Yates Shuffle 的时间复杂度是 O(n)，其中 n 是数组的长度。这是因为算法需要对数组中的每个元素进行一次迭代，并在每次迭代中进行一次交换。