如何从数组c中获取n个随机值++

Question

我想从数组中取出n随机值。 我可以在Python中使用x=random.sample(listName, numberOfValuesNeeded)

[code]
#include <iostream>
#include <ctime>
#include <cstdlib>
#include <algorithm>
#include <iterator>

using namespace std;

int main()
{
    const int MAX_Name=100;

    srand((unsigned)time( NULL));

    // Names
    string PsDisp[MAX_Name]={"Alberto", "Bruno", "Carlo", "Dario", "Elio", "Francesco", "Giovanni", "Luca", "Marco", "Nicola", "Oreste", "Pietro",   "Rino", "Sandro", "Tonino", "Valerio", "Vittorio"};


    for(int x=1; x<=6; x++)
    {
        random_shuffle(begin(PsDisp), end(PsDisp));

        cout << x << ": " << endl; // snomething missing before endl
    }

    return 0;
}

我想在屏幕上打印：

1: random name1
2: random name3 ...
6: random name6

Answer 1

如果不关心重复，可以生成6个随机索引并打印相应的值，如下所示：

for(int x=1; x<=6; x++)
{
    cout << x << ": " << dispNames[rand() % MAX_Name] << endl;
}

Answer 2

您可以使用一种称为Reservoir Sampling的技术。它只在输入上迭代一次，因此需要O（n）。这是你的样本代码，工作C++ 11储层采样：

#include <iostream>
#include <string>
#include <vector>
#include <random>
#include <iterator>
#include <algorithm>
#include <cassert>


template<class InputIt, class Generator>
std::vector<typename std::iterator_traits<InputIt>::value_type> sample(InputIt first, InputIt last, size_t n, Generator& engine) {
    assert(distance(first, last) >= n);
    InputIt nth = next(first, n);
    std::vector<typename std::iterator_traits<InputIt>::value_type> result{first, nth};
    size_t k=n+1;
    for (InputIt it = nth; it != last; ++it, ++k) {
        size_t r = std::uniform_int_distribution<size_t>{0, k}(engine);
        if (r<n)
            result[r] = *it;
    }
    return result;
}


using namespace std;

int main()
{

    string xs[] = {"Alberto", "Bruno", "Carlo", "Dario", "Elio", "Francesco", "Giovanni", "Luca", "Marco", "Nicola", "Oreste", "Pietro",   "Rino", "Sandro", "Tonino", "Valerio", "Vittorio"};

    mt19937 engine{random_device{}()};
    vector<string> ys = sample(begin(xs), end(xs), 5, engine);

    for (const string& s : ys)
        cout << s << endl;

    return 0;
}

Answer 3

Python的^{}返回samples而不替换。这意味着你不能得到同一个元素两次。在

你的算法显然不一样。如果在获得每个值后重新改组，则替换这些值。但是有一个简单的方法可以解决这个问题：只需在循环外洗牌一次，而不是每次都在循环中。在

这意味着循环非常简单：您只想打印无序dispNames中的前6个数字。所以：

random_shuffle(begin(dispNames), end(dispNames));
for (int x=1; x<=6; x++) {
    cout << x << ": " << dispNames[x-1] << endl;
}

一些旁注：

• random_shuffle已弃用。默认PRNG的shuffle也是如此。这是一个很好的理由；即使你不在乎密码的随机性或任何花哨的东西，你仍然想使用一个特定的PRNG和新版本的shuffle，只是为了便于移植获得统一的分布。在
• 从0到<6比从1到{}更正常。这意味着你不需要x-1。在
• 使用迭代器而不是索引会更好；这样即使用其他可随机访问的类型而不是数组替换dispNames，同样的代码也可以工作。在

---

从17个样本中选出6个样本，这是可以的。（好吧，只要可以接受破坏性地修改数组，Python的random.sample不能做到这一点……但是如果这是一个问题，用复制无序替换它并不难，或者只是一个副本加上一个破坏性的无序处理…）

但是如果你的价值观太大了，你需要考虑效率。洗牌本质上需要O（N）时间，因为它必须洗牌大多数N个值。但是从N中挑选K值不需要那么长时间。（如果您切换到复制随机播放，您还将添加O（N）空间，这也不是必需的。）

<>我不认为C++中有一个等价的STDLIB，但没关系，值得学习如何自己实现，这样你就能明白它在做什么。有几种不同的选择：你可以在排列生成器（C++中确实有STDLIB）的顶部建立它，或者在下一个素数的大的线性同余生成器之上，比列表的长度大（抛出太大的值），或者部分Fisher Yates洗牌而不是完整的，或者其他我没想到的事情。（还有一些在特定情况下非常简单和快速，但在一般情况下不是这样的——例如，如果K很小，只需选择替换并跟踪以前的选择很有效，但是如果K是N的一个相当大的块，则非常可怕。）

或者，当然，你可以read the CPython source，这是一个很好的方法来找出如何编写C++代码，它将与Python做完全相同的事情。在