返回题库

幸运泡泡

Lucky Bubble

专题
Probability / 概率
难度
L3

题目详情

Steven 收到了一个大小为 nn 的数组，其中填充了数字 1,2,3…,n1,2,3\dots,n 的随机排列。他执行一轮冒泡排序算法，数组就已排序。发生这种情况的概率是多少？

Steven received an array of size nn filled with a random permutation of the numbers 1,2,3…,n1,2,3\dots,n. He performs one pass of the bubble sort algorithm and the array becomes sorted. What is the probability of this happening?

解析

总共有 n!n! 可能的 nn 数字排列，我们只需要在一次冒泡排序算法之后最终出现在排序数组中的排列。

单遍运行可编码为 00（无交换）或 11（交换）的 n−1n-1 操作，为冒泡排序算法的最后一遍留下总共 2n−12^{n-1} 可能的交换组合。

为了得到概率，我们将该数字除以排列总数： P(Sorted after one pass)=2n−1n!\begin{equation} P(\textrm{Sorted after one pass}) = \frac{2^{n-1}}{n!} \end{equation}

Original Explanation

In total there are n!n! possible permutations of nn numbers and we want only the permutations that end up in a sorted array after a single pass of the bubble sort algorithm.

A single pass runs n−1n-1 operations that could be encoded as a 00 (no swap) or 11 (swap), leaving a total of 2n−12^{n-1} possible swap combinations for the last pass of the bubble sort algorithm.

To get the probability, we divide this number by the total number of permutations:

P(Sorted after one pass)=2n−1n!\begin{equation} P(\textrm{Sorted after one pass}) = \frac{2^{n-1}}{n!} \end{equation}