c++ - ランダムな順序で配列を反復処理する

Question

N一連の要素 (または など)が与えられた場合、その要素をランダムな順序で反復処理し、各要素を 1 回だけアクセスする効率的な方法はありますかstd::vector。T*解決策は、シャッフルされたインデックスを持つ追加の配列を作成しないようにする必要があります。

編集：

また、元のインデックスを追跡できる必要があります

Answer 1

を使用するstd::random_shuffleと、コードは次のようになります。

std::random_shuffle ( myvector.begin(), myvector.end() );  // in place no extra array
for (std::vector<int>::iterator it=myvector.begin(); it!=myvector.end(); ++it)
   std::cout << ' ' << *it;

Answer 2

ええと、追加の配列を作成することの制限については完全にはわかりません。しかし基本的には、インデックスをランダムに生成してから、既にヒットしたインデックスにヒットした場合は再生成を繰り返します。必ずしも効率的であるとは限りません。しかし、境界が確実に O(n^2) と O(n!) (おそらく (O(n^n)) の間であると推測する危険があります。ちょっとした作業で、それをきれいにして、ほとんどの場合、n^2 になります。