1

我希望有人可以帮助我回答以下问题。谢谢！

这是 Permute-By-Sorting 算法的伪代码：

Permute-By-Sorting (A)

    n = A.length

    let P[1..n] be a new array

    for i = 1 to n

        P[i] = Random (1,n^3)

    sort A, using P as sort keys

在上述算法中，数组 P 表示数组 A 中元素的优先级。第 4 行在 1 和 n^3 之间选择一个随机数。

问题是 P 中所有优先级都是唯一的概率是多少？以及如何获得概率？

4

5 回答 5

1

其他人已经给了你概率计算，但我认为你可能问错了问题。

我假设您询问优先级唯一性的概率的原因，以及首先选择 n^3 的原因是因为您希望它们是唯一的，并且选择相对于 n 的较大范围似乎是实现唯一性的合理方式。

确保值是唯一的要容易得多。只需使用数字 1 .. n 填充优先级数组，然后使用Fisher-Yates 算法（又名算法 P，来自计算机编程艺术，第 2 卷，半数字算法，Donald Knuth 编写）对它们进行洗牌。

然后将使用已知的唯一优先级值执行排序。

（还有其他获得随机排列的方法。可以使用阶乘数（或阶乘数系统）生成序列的第 n 个字典排列，从而为 [ 1 .. n!]。）

于 2012-06-01T22:12:20.250 回答
1

您正在n从中选择数字1...n^3并询问它们都是唯一的概率是多少。

有一些(n^3) P n = (n^3)!/(n^3-n)!方法可以唯一地选择 n 个数字，也(n^3)^n可以选择 n 个总数。

所以数字唯一的概率只是第一个方程除以第二个方程，它给出

3！     _
--------------
 (n 3 -n)！n 3n
于 2012-06-01T17:57:43.427 回答
1

调和已经给出的答案：对于选项 i = 0，...，n - 1，鉴于尚未选择重复项，对于第 i 个值，总共有 n^3 - i 个非重复选择 n^3 . 因此概率是 (1 - i/n^3) 的 i = 0, ..., n - 1 的乘积。

sdcwc 使用联合绑定来将此概率降低 1 - O(1/n)。事实证明，这个估计基本上是正确的。证明草图是 (1 - i/n^3) 是 exp(-i/n^3 + O(i^2/n^6))，所以乘积是 exp(-O(n^2)/ n^3 + O(n^-3))，大于等于 1 - O(n^2)/n^3 + O(n^-3) = 1 - O(1/n)。我相信 math.SE 的优秀人士会很乐意为您“正确”地进行这种推导。

于 2012-06-01T19:09:54.393 回答
0

所以排序部分是无关紧要的

假设“随机”是真正的随机，概率只是

      n^3!
----------------
 (n^3-n)!n^(3n)
于 2012-06-01T17:30:22.763 回答
0

设 A ij为事件：第 i 个和第 j 个元素发生碰撞。显然 P(A ij )=1/n 3。

最多有 n 2对，因此至少一次碰撞的概率最多为 1/n。

如果您对确切的事情感兴趣，请参阅 BlueRaja 的答案，但在随机算法中，通常足以给出这种类型的界限。

于 2012-06-01T18:08:19.547 回答