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アルゴリズム（The Art of Computer Programming、第2巻、Seminumerical Algorithms、Donald KnuthによるアルゴリズムP）を使用してシャッフルします。

次に、既知の一意の優先度値を使用してソートが実行されます。

（ランダム順列を取得する方法は他にもあります。階乗数（または階乗進法）を使用してシーケンスのn番目の字句順列を生成することができるため、[でランダムに選択された値の順列を生成します。 1 .. n！]。）

于 2012-06-01T22:12:20.250 に答える
1

nから数を選択1...n^3し、それらがすべて一意である確率を尋ねています。

n個(n^3) P n = (n^3)!/(n^3-n)!を一意に(n^3)^n選択する方法と、n 個の合計を選択する方法があります。

したがって、数値が一意である確率は、最初の式を 2 番目の式で割ったものにすぎません。

     n 3 !
--------------
 (n 3 -n)! n 3n
于 2012-06-01T17:57:43.427 に答える
1

すでに与えられた答えを調整するには: 選択 i = 0, ..., n - 1 に対して、まだ重複が選択されていない場合、i 番目の値の合計 n^3 の重複しない選択が n^3 - i あります。 . したがって、確率は (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

A ijをイベントとします。i 番目と j 番目の要素が衝突します。明らかに、Ｐ（Ａｉｊ）＝１／ｎ３である。

最大 n 2ペアがあるため、少なくとも 1 つの衝突の確率は最大 1/n です。

正確なことに興味がある場合は、BlueRajaの回答を参照してください。ただし、ランダム化されたアルゴリズムでは、通常、このタイプの境界を与えるだけで十分です。

于 2012-06-01T18:08:19.547 に答える
0

したがって、ソート部分は無関係です

「ランダム」が実際のランダムであると仮定すると、確率はちょうど

      n^3!
----------------
 (n^3-n)!n^(3n)
于 2012-06-01T17:30:22.763 に答える