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的详细步骤：

初始化：

算法开始时，数组中的元素按照其原始顺序排列。

迭代：

从数组的最后一个元素开始，依次向前迭代到第一个元素。

随机选择：

对于当前迭代的位置（假设为i），生成一个[0, i]范围内的随机整数 j。

交换元素：

将当前位置（i）的元素与随机选择位置（j）的元素进行交换。

递减迭代：

继续迭代，减小当前位置，直到第一个元素。

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

Fisher-Yates

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

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

123456789101112131415import randomdef 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

是数组的长度。这是因为算法需要对数组中的每个元素进行一次迭代，并在每次迭代中进行一次交换。