Problem 367

Bozo sort

Bozo sort, not to be confused with the slightly less efficient bogo sort, consists out of checking if the input sequence is sorted and if not swapping randomly two elements. This is repeated until eventually the sequence is sorted.

If we consider all permutations of the first 4 natural numbers as input the expectation value of the number of swaps, averaged over all 4! input sequences is 24.75.
The already sorted sequence takes 0 steps.

In this problem we consider the following variant on bozo sort.
If the sequence is not in order we pick three elements at random and shuffle these three elements randomly.
All 3!=6 permutations of those three elements are equally likely.
The already sorted sequence will take 0 steps.
If we consider all permutations of the first 4 natural numbers as input the expectation value of the number of shuffles, averaged over all 4! input sequences is 27.5.
Consider as input sequences the permutations of the first 11 natural numbers.
Averaged over all 11! input sequences, what is the expected number of shuffles this sorting algorithm will perform?

Give your answer rounded to the nearest integer.

Bozo排序

Bozo排序常常会和稍微更没效率的Bogo排序相混淆，前者先检查输入序列是否是有序的，如果不是，则随机交换两个元素，不断重复这个过程，直到序列有序为止。

如果我们将前4个自然数的所有排列作为输入，这4!种输入序列所需交换次数的期望值平均是24.75。
已经有序的序列所需操作次数为0次。

在本题中，我们考虑Bozo排序的以下变种。
如果序列并不有序，我们随机选择三个元素，再随机重排这三个元素。
这三个元素所有3!=6种排列都等可能发生。
已经有序的序列所需操作次数为0次。
如果我们将前4个自然数的所有排列作为输入，这4!种输入序列所需重排次数的期望值平均是27.5。
现在考虑将前11个自然数的所有排列作为输入。
这11!种输入序列所需重排次数的期望值平均是多少？

将你的答案四舍五入到最近的整数。