概率疑点

Question

我正在解决一个问题—— 有一组最初无序的数字。目标是对其进行排序。排序应该通过打乱数字直到它们落入正确的位置来完成（是的，Bogosort'ish :)）打乱有一个优化，如果打乱后，任何靠近列表开头或结尾的元素都会落入其中它们的正确位置，这些元素将被固定，其余元素将使用上述相同的逻辑进行洗牌。问题是计算对最初无序的一组数字（例如 6）进行排序所需的平均 f 次洗牌次数。 我知道它是沿着概率线的分布序列，但无法将其完全归零。任何正确方向或方法的建议/建议将不胜感激。

谢谢

Answer 1

这可以递归计算。

• 长度为 0 的列表平均需要 0 次洗牌。 f(0) = 0。
• 长度为 1 的列表平均需要 0 次洗牌。 f(1) = 0。
• 混洗后长度为 2 的列表有几种可能性：
  • 它已经排序（50% 的机会）：0 次洗牌。
  • 尚未排序（50% 的可能性）：
    • 随机排序：1 次随机播放。
    • 洗牌没有帮助，我们需要再试一次：1 + f(2) 洗牌。

这可以写成：

f(2) = ((1/2) * 0) + ((1/2) * (1/2) * 1) + ((1/2) * (1/2) * (1 + f(2)).
f(2) = 2/3

您可以通过将输入减少到已经解决的较小输入来继续以这种方式获得更大的输入。