6

CLRS を研究していて、シャッフル アルゴリズムに問題があることがわかりました。これは均一にランダムな順列を生成しますか?

1 PERMUTE-WITH-ALL-IDENTITY(A)
2    n = A.length
3    for i = 1 to n
4        swap A[i] with A[RANDOM(1,n)]
5        swap A[i] with A[RANDOM(i+1,n)]

私の主張: いいえ、そうではありません。なぜなら、4 行目により、n^n 通りの順列が可能になるからです。そして、n で割り切れないのです! これは、異なる順列の数です。

私の推論が正しいか確認していただけますか？

4

2 に答える 2

3

まず、疑似コードにバグがあると思います。4 行目では、i = n のときに境界エラーがあると思います。これは、n+1 と n の間の乱数を要求するからです。以下では、コードが次のようになっていると仮定して、これを修正しました。

1 PERMUTE-WITH-ALL-IDENTITY(A)
2    n = A.length
3    for i = 1 to n
4        swap A[i] with A[RANDOM(1,n)]
5        swap A[i] with A[RANDOM(i,n)]

これがコードである場合、答えはノーだと思います。これは一様にランダムな順列を生成しません。これが事実であるという数学的な証明はありませんが、可能性のあるすべてのパスをブルートフォースしPERMUTE-WITH-ALL-IDENTITY、各順列が生成される回数をカウントする C++ コードがあります。私はそのコードを実行し、0 から 4 までの長さのシーケンスの順列でアルゴリズムをテストしました。

コードは次のとおりです。

#include <iostream>
#include <map>
#include <vector>
#include <algorithm>
using namespace std;

/* Maximum size of a sequence to permute. */
const size_t kMaxSize = 4;

/**
 * Given a frequencies map associating permutations to the number of times
 * that we've seen them, displays a visual report of the permutations
 * and their frequencies.
 *
 * @param frequencies The frequencies map.
 */
void reportResults(const map<vector<int>, size_t>& frequencies, size_t size) {
  cout << "Report for size " << size << endl;
  cout << "===================================================" << endl;  

  /* Print out the map. */
  cout << "  Map entries:" << endl;
  for (const auto& entry: frequencies) {
    cout << "    ";
    for (const auto& num: entry.first) {
      cout << num;
    }
    cout << ": " << entry.second << endl;
  }

  cout << "===================================================" << endl;
  cout << endl << endl;
}

/**
 * Traces through all possible executions of the algorithm, recording
 * the number of times that each outcome occurs. This algorithm uses
 * exhaustive recursion to explore the full space, assuming that the
 * underlying random generator is uniform.
 *
 * @param elems The elements in the sequence. It's assumed that initially
 *    these are in sorted order, but as the algorithm progresses it will
 *    become progressively more permuted.
 * @param frequencies A map from permutations to the number of times that
 *    they appear.
 * @param index The index through the main loop that we are currently in.
 *    This is the variable 'i' in the pseudocode.
 * @param size The length of the vector. This isn't strictly necessary,
 *    but it makes the code a bit cleaner.
 */
void recPopulate(const vector<int>& elems,
                 map<vector<int>, size_t>& frequencies,
                 size_t index, size_t size) {
  /* If we've finished permuting everything, record in the frequency map
   * that we've seen this permutation one more time.
   */
  if (index == size) {
    frequencies[elems]++;
  } else {
    /* For all possible pairs of a first swap and a second swap, try that
     * out and see what happens.
     */
    for (size_t i = 0; i < size; i++) {        // First swap index
      for (size_t j = index; j < size; j++) {  // Second swap index
        /* Make a clean copy of the vector to permute. */
        vector<int> newElems = elems;

        /* Perform the swaps. */
        swap(newElems[i], newElems[index]);
        swap(newElems[j], newElems[index]);

        /* Recursively explore all possible executions of the algorithm
         * from this point forward.
         */
        recPopulate(newElems, frequencies, index + 1, size);
      }
    }
  }
}

/**
 * Traces through all possible executions of the proposed algorithm,
 * building a frequency map associating each permutation with the
 * number of possible executions that arrive there.
 *
 * @param size The number of elements in the initial sequence.
 * @return A frequency map from permutations to the number of times that
 *    permutation can be generated.
 */
map<vector<int>, size_t> populateFrequencies(size_t size) {
  /* Create the sequence 0, 1, 2, ..., size - 1 */
  vector<int> elems(size);
  iota(elems.begin(), elems.end(), 0);

  map<vector<int>, size_t> frequencies;
  recPopulate(elems, frequencies, 0, elems.size());
  return frequencies;
}

int main() {
  for (size_t size = 0; size <= kMaxSize; size++) {
    map<vector<int>, size_t> frequencies = populateFrequencies(size);
    reportResults(frequencies, size);
  }
}

このプログラムは、順列ごとに、その順列を生成するアルゴリズムを通る可能な実行パスの数を示すレポートを生成します。4 つの要素の順列の出力を以下に示します。ここでの数値は同じではないため、各実行パスの可能性が等しいとすると、アルゴリズムは一様にランダムではないと結論付けることができます。

Report for size 4
===================================================
  Map entries:
    0123: 214
    0132: 268
    0213: 267
    0231: 316
    0312: 242
    0321: 229
    1023: 268
    1032: 322
    1203: 312
    1230: 349
    1302: 287
    1320: 262
    2013: 242
    2031: 283
    2103: 233
    2130: 262
    2301: 252
    2310: 240
    3012: 213
    3021: 208
    3102: 204
    3120: 187
    3201: 248
    3210: 236
===================================================

上記の分析は、次の事実に基づいています。

  1. 私のコードは正しく、
  2. 疑似コードの私の解釈は正しいです。

これらのいずれかが間違っている場合は、この回答を撤回または編集していただければ幸いです。ここで間違っていたら教えてください！

お役に立てれば！

于 2015-06-08T17:28:20.017 に答える
1

上記の分析は、カイが 147、自由度が 23 であることを示唆しています。これは、P 値が < 0.00001 であることを意味します。これは、一様分布と推定される適合度が非常に低いことを示しています。

しかし。

合計サンプル数は 6144 しかないようです。ランダム性を見ているなら、もっと多くの実行が適切だと思ったでしょう。1000回程度実行すると、P値がより有利な位置に移動する可能性があります。ただし、実行間で乱数発生器を再シードしないでください。

于 2015-07-27T03:02:25.857 に答える