std::vector内の要素をランダムにシャッフルし、いくつかの操作の後、元の順序を復元する適切な方法を理解するのに問題があります。これはかなり些細なアルゴリズムであるべきだと私は知っていますが、私はあまりにも疲れていると思います...
カスタム乱数ジェネレータークラスを使用するように制約さstd::random_shuffleれているため、元の順序も保持する必要があるため、とにかく役に立たない、を使用できないと思います。したがって、私のアプローチは、std::map次のように、元の位置とランダムな位置の間のマッピングとして機能するを作成することでした。
std::map<unsigned int, unsigned int> getRandomPermutation (const unsigned int &numberOfElements)
{
std::map<unsigned int, unsigned int> permutation;
//populate the map
for (unsigned int i = 0; i < numberOfElements; i++)
{
permutation[i] = i;
}
//randomize it
for (unsigned int i = 0; i < numberOfElements; i++)
{
//generate a random number in the interval [0, numberOfElements)
unsigned long randomValue = GetRandomInteger(numberOfElements - 1U);
//broken swap implementation
//permutation[i] = randomValue;
//permutation[randomValue] = i;
//use this instead:
std::swap(permutation[i], permutation[randomValue]);
}
return permutation;
}
上記のアルゴリズムがランダム置換の適切な実装であるかどうかはわかりません。したがって、改善を歓迎します。
さて、これが私がこの順列マップを利用することに成功した方法です：
std::vector<BigInteger> doStuff (const std::vector<BigInteger> &input)
{
/// Permute the values in a random order
std::map<unsigned int, unsigned int> permutation = getRandomPermutation(static_cast<unsigned int>(input.size()));
std::vector<BigInteger> temp;
//permute values
for (unsigned int i = 0; i < static_cast<unsigned int>(input.size()); ++i)
{
temp.push_back(input[permutation[i]]);
}
//do all sorts of stuff with temp
/// Reverse the permutation
std::vector<BigInteger> output;
for (unsigned int i = 0; i < static_cast<unsigned int>(input.size()); ++i)
{
output.push_back(temp[permutation[i]]);
}
return output;
}
このアルゴリズムには1つしか使用できないはずだと言われていますstd::vector<BigInteger>が、現時点では、最適なソリューションを見つけることができません。正直なところ、私はのデータをあまり気にしないので、データをinput非定数にして上書きし、コピーの作成をスキップすることもできますが、問題はアルゴリズムを実装する方法ですか？
こういうことをすると、足を撃ってしまうんですよね？:)
for (unsigned int i = 0; i < static_cast<unsigned int>(input.size()); ++i)
{
BigInteger aux = input[i];
input[i] = input[permutation[i]];
input[permutation[i]] = aux;
}
編集：「フィッシャー-イェーツ」シャッフルの使用に関するスティーブの発言に続いて、getRandomPermutationそれに応じて関数を変更しました。
std::map<unsigned int, unsigned int> getRandomPermutation (const unsigned int &numberOfElements)
{
std::map<unsigned int, unsigned int> permutation;
//populate the map
for (unsigned int i = 0; i < numberOfElements; i++)
{
permutation[i] = i;
}
//randomize it
for (unsigned int i = numberOfElements - 1; i > 0; --i)
{
//generate a random number in the interval [0, numberOfElements)
unsigned long randomValue = GetRandomInteger(i);
std::swap(permutation[i], permutation[randomValue]);
}
return permutation;
}