C++ - 随机选择字符串而不选择它超过一次

Question

我手上满是对象，每个对象都包含几个字符串。现在它被设置为结构，每个结构包含一个映射，键为 1...n，每个字符串一个(map<int,string> strs)，如果存在更好的方法，可以更改。我需要在不重叠的情况下随机访问所有这些字符串，并且知道我已经完成了。我怎样才能做到这一点，无论是使用 map 还是其他数据结构？谢谢。

Answer 1

这是 Fisher-Yates shuffle 的一些代码:

template <class T>
std::vector<T> shuffle(std::vector<T> &vect)
{
    std::vector<T> shuffled = vect;
    for(int i = shuffled.size()-1; i >= 1; i--) {
        int idx = rand() % (i+1);
        T tmp = shuffled[idx];
        shuffled[idx] = shuffled[i];
        shuffled[i] = tmp;
    }
    return shuffled;
}

这将接受一个 vector ，并以随机顺序返回它的一个拷贝。如果你有一个字符串 vector ，你可以像这样使用它(我在这里使用 c++11):

int main()
{
    srand(time(NULL));
    std::vector<std::string> strs = {"foo", "bar", "baz", "stack", "overflow"};
    for(auto &str : shuffle(strs)) {
        std::cout << str << std::endl;
    }
    return 0;
}

当然，如果你像我一样懒惰，<algorithm> 中总有 random_shuffle() 函数。 :

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

int main()
{
    std::vector<std::string> strs = {"foo", "bar", "baz", "stack", "overflow"};
    std::random_device rd;
    std::mt19937 g(rd()); // Use a good random number generaor
    std::random_shuffle(strs.begin(), strs.end(), g); // this does the shuffle
    for(auto &str : strs) {
        std::cout << str << std::endl;
    }
    return 0;
}

希望这对您有所帮助!