project euler问题367

〇〇

Problem 367
14 January 2012


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.


“挑2和交换”24.75和“挑3和洗牌”27.5怎么推导？

〇〇

既然有可能无限循环，那么任何数+无穷的平均数是无穷

gracias

project euler 362 你是咋解的啊

mathe

4!的状态还是很好处理的。而目标状态是什么并不重要，任意一个结果都相同。
而不同状态之间的转移概率可以构成一个n!对称稀疏阵A.可以将对称阵中目标状态对应的行和列删除，得到（n!-1)阶矩阵B.b为全1的向量，于是方程
(I-B)x=b
的解就对应各个状态到达目标状态的平均次数。于是解的所有分量的和除以n!就是结果了。
而当n=11时，状态数目达到40M,幸好矩阵是稀疏矩阵，储存还不是问题，但是求解应该要使用迭代法，这里应该可以使用雅可比迭代法，只是不知道收敛速度如何