如何从数组 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

Python 的 random.sample returns 个样本 没有替换 。这意味着您不能两次获得相同的元素。

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

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

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

一些旁注：

random_shuffle 已弃用。 shuffle 默认 PRNG 也是如此。这是有充分理由的；即使您不关心密码随机性或任何花哨的东西，您仍然希望使用特定的 PRNG 和 shuffle 的新版本，只是为了便携地获得统一分布。
从0数到<6比从1数到<=6更正常。这意味着您不需要 x-1.
使用迭代器代替索引会更好；那么即使您将 dispNames 替换为其他一些可随机访问的类型而不是数组，相同的代码也会起作用。

从 17 个样本中挑选 6 个样本，这很好。（好吧，只要破坏性地修改数组是可以接受的就没问题，Python 的 random.sample 不这样做......但如果这是一个问题，用复制洗牌代替它并不难，或者只是一个副本加上一个破坏性的洗牌......）

但是如果你的值变得太大，你需要考虑效率。洗牌本质上需要 O(N) 时间，因为它必须洗牌 N 个值中的大部分。但是从 N 中挑选 K 值不应该花那么长时间。（如果你切换到复制洗牌，你还添加了 O(N) space，这也不是必需的。）

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

或者，当然，您可以 read the CPython source，这是了解如何编写与 Python.[=25= 完全相同的 C++ 代码的好方法]

Answer 3

您可以使用一种称为 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;
}

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

How to fetch 'n' random values out of an array c++

c++

python

arrays

random