均匀随机排列

概述

均匀随机排列 是指 $n$ 个元素的 $n!$ 种排列中，每一种排列以等概率 $1/n!$ 出现的随机排列。生成均匀随机排列是随机化算法的基本操作之一。

定义

均匀随机排列

给定 $n$ 个元素的集合，一个均匀随机排列（uniform random permutation）是从该集合的所有 $n!$ 种排列中，按照均匀分布随机选取的一种排列。即每种排列被选中的概率均为 $1/n!$。

核心性质

• 排列总数：$n$ 个元素共有 $n!$ 种不同的排列。
• 均匀性要求：每种排列必须以恰好 $1/n!$ 的概率产生，这是验证排列算法正确性的关键标准。
• 两种经典生成方法：
  1. PERMUTE-BY-SORTING：为每个元素分配一个随机优先级，然后按优先级排序。时间复杂度 $O(n\lg n)$（受排序算法限制），需要额外的随机数生成。
  2. RANDOMIZE-IN-PLACE（原址排列）：在位置 $i$ 处，从 $[i,n]$ 中随机选取一个元素与位置 $i$ 的元素交换。时间复杂度 $\Theta (n)$，空间复杂度 $O(1)$，是更优的方法。
• 引理 5.3：RANDOMIZE-IN-PLACE 过程产生均匀随机排列。
• 引理 5.4：在 RANDOMIZE-IN-PLACE 中，对每个 $i$，$A[i]$ 成为原来第 $j$ 个元素的概率恰好为 $1/n$。

章节扩展

第5章：概率分析与随机化算法

• 5.3 随机化算法 详细介绍了 PERMUTE-BY-SORTING 和 RANDOMIZE-IN-PLACE 两种方法，并给出了正确性证明。
• RANDOMIZE-IN-PLACE 是 随机化算法 中随机化快速排序的基础操作。

参见

• 随机化算法
• 概率分析