c++ - C++ - 文字列を複数回選択せずにランダムに選択する

Question

それぞれが複数の文字列を含むオブジェクトでいっぱいの手があります。現在、各文字列 ( map<int,string> strs) に対して 1 つのキー 1...n を持つマップを含む構造体として設定されていますが、より良い方法が存在する場合は変更できます。オーバーラップせずにこれらすべての文字列にランダムにアクセスし、完了したことを知る必要があります。マップまたは別のデータ構造を使用して、これを行うにはどうすればよいですか? ありがとう。

Answer 1

恐ろしい解決策です。これをしないでください。大きな候補ベクトルの場合は非常に遅く、これには n 乗の複雑さがあります。シャッフルの方が優れており、線形の複雑さがあります。

std::vector<int> RandomThing(int number, int min, int max)
{
    assert(!"RandomThing" && min < max);
    std::vector<int> candidates;
    for(int i=min; i<max; i++)
        candidates.push_back(i);

    std::vector<int> result;
    for(int i=0; i<number;)
    {
        int candidate_index = rand() % candidates.size();
        result.push_back(candidates[candidate_index]);

        std::vector<int>::iterator it = candidates.begin();
        std::advance(it, candidate_index);
        candidates.erase(it);
    }
    return result;
}