0%

# Problem 595

## Incremental Random Sort

A deck of cards numbered from 1 to n is shuffled randomly such that each permutation is equally likely.

The cards are to be sorted into ascending order using the following technique:

1. Look at the initial sequence of cards. If it is already sorted, then there is no need for further action. Otherwise, if any subsequences of cards happen to be in the correct place relative to one another (ascending with no gaps), then those subsequences are fixed by attaching the cards together. For example, with 7 cards initially in the order 4123756, the cards labelled 1, 2 and 3 would be attached together, as would 5 and 6.
2. The cards are ‘shuffled’ by being thrown into the air, but note that any correctly sequenced cards remain attached, so their orders are maintained. The cards (or bundles of attached cards) are then picked up randomly. You should assume that this randomisation is unbiased, despite the fact that some cards are single, and others are grouped together.
3. Repeat steps 1 and 2 until the cards are sorted.

Let S(n) be the expected number of shuffles needed to sort the cards. Since the order is checked before the first shuffle, S(1) = 0. You are given that S(2) = 1, and S(5) = 4213/871.

## 改进随机排序

1. 查看卡片的初始顺序。如果卡片已经有序，那么没必要采取额外的操作。否则，如果卡片中有任何子序列已经有序（连续的上升序列），则这些子序列会被固定在一起。例如，如果7张卡片的初始顺序是4123756，那么标号为1，2和3的卡片和标号为5和6的卡片将会分别固定在一起。
2. 将这些卡片扔到空中“洗牌”，注意已经被固定在一起的卡片在这个过程中不会被分开，因此其顺序不发生改变。这些卡片（或卡片组）然后被随机地捡起来，你可以假设这一随机操作是无偏的，即使其中有些卡片只有一张，而有些则被固定在一块儿。
3. 重复步骤1和2，直到卡片已经有序。