c++ - C++でポインタのリストをシャッフルする方法は?

Question

C++ でポインタの stl リストをシャッフルする方法は? クラス Player にポインターの stl ベクトルがあり、次のようにシャッフルします

std::random_shuffle(players.begin(), players.end());

ランダムアクセスを必要としないシャッフルリストのアルゴリズムは既にありますか、またはリストをベクトルに変換する必要があります=>シャッフル=>リストに戻す? よりエレガントなソリューションはありますか?

Answer 1

ランダム シャッフル アルゴリズムは、特定の要素をランダムに選択された要素と交換します。リストを繰り返しトラバースして要素を取得するのは非常に非効率的です (つまり、O(n^2)操作になります)。

そのため、リストを配列に一度コピーし、ランダムなシャッフルを実行して、リストを復元する方が (より高速に) 優れています。それ3*nはまだO(n).

Answer 2

std::random_shuffleランダムなイテレータが必要です。ベクターはこれをサポートしていますが、リストはサポートしていません。どうですかstd::deque、それは一種のベクトルと一種のリストのようなものです。

Answer 3

あなたの問題は面白かったです。それで、何かを書いてみて、最終的にこれを思いつきました。

    //---------- sample List initialization ------
    list<string> lst;
    lst.push_back("A");
    lst.push_back("B");
         ....
    lst.push_back("Y");
    lst.push_back("Z");

    #define LIST_SIZE 26
    //--------------------------------------------

    //------------- Shuffle Algorithm ------------
    unordered_multimap<int,string> mymap;
    int HashKeys[LIST_SIZE];
    srand((int)time(NULL) * (int)clock());

    for(int i = 0; i<LIST_SIZE; i++) // loop 'n' times
    {
        HashKeys[i] = rand(); // O(c) operation
    }

    for(int i = 0;lst.size() > 0; i++) // loop 'n' times
    {
         // O(n) operation ( varies from O(c) to O(n) according to the situations )
        mymap.insert(std::make_pair<int,string>(HashKeys[rand() % LIST_SIZE],lst.front()));
        lst.pop_front(); // O(c) operation
    }

    unordered_multimap<int,string>::iterator it;
    for(int i = 0; i < LIST_SIZE ;i++) // loop 'n' times
    {
        while(mymap.count(HashKeys[i]) > 0) // unpredictable
        {
            it = mymap.find(HashKeys[i]); // O(c) for single O(n) for multi
                    // ...USAGE...
            cout << it->second << endl;
                    lst.push_back(it->second);
                    //............
            mymap.erase(it); // O(c) operation
        }
    }
    //-------------------------------------------------

ハッシュマップに同じキーに複数の値がある場合、時間の複雑さは O(n^2) です。それ以外の場合、時間計算量は O(n) です。したがって、すべては機能に依存します(rand() % LIST_SIZE)