c++11 - C++,在1-n的范围内生成m个不同的随机数

Question

不知道怎么搜英文的解决。只好来这边问了

C++里面，想实现比如：

范围给定为1-25，然后要求生成5个随机数，那么可能的结果是：1，2，8，4，5，而不会是：5，4，3，5，5（出现多个同一数字）。

Answer 1

将 n 个数洗牌后，取前 m 个。
可以参考 Fisher-Yates 。

优化：用 Fisher-Yates 算法决定前 m 个数即可。

Answer 2

使用 shuffle（C++11、C++14）或 random_shuffle（C++98）来让包含 1 到 n 的数组随机排序，取前 m 个即可。

http://en.cppreference.com/w/cpp/algorithm/random_shuffle

下面的代码需要支持 C++11 的编译器才能编译。

#include <random>
#include <algorithm>
#include <iterator>
#include <iostream>

int main() {
    // assume m is 5 and n is 25.
    int m = 5;
    int n = 25;

    // initialize numbers.
    std::vector<int> v(n);
    std::iota(v.begin(), v.end(), 1);

    // do random shuffle.
    std::random_device rd;
    std::mt19937 g(rd());
    std::shuffle(v.begin(), v.end(), g);

    // show first m numbers.
    std::copy_n(v.begin(), m, std::ostream_iterator<int>(std::cout, " "));
    std::cout << std::endl;

    return 0;
}

Answer 3

我C++基本不会，不过我有两个思路：

1. 取到一个随机数之后就记录下来（比如java中可以用hashmap来记录），然后下次去随机数的时候，如果已经被取了，就重新取，直至成功。不过这个方法不好的地方在于如果要取的随机数数量比较大，效率较低。

2. 一个int数组1-25（数组下标范围），取随机数，如果随机数不是最后一个数，将取到的数移到数组最后一位，然后第二次取1-24（数组下标范围），取到的移到最后一位，。。。。。依次迭代下去即可。

Answer 4

csdn上的一种算法

Answer 5

srand((unsigned)time(NULL));
rand()%n

Answer 6

通用的有两种方法：
1.重复再随机
这种方法是在[L,R]中先随机一个数，如果这个数之前取过，那么重复这个过程，直到取到不同的数为止。
不过这种方法在n个数取m个随机（m接近于n）时，时间复杂度将会很大。
这种方法的时间复杂度最坏为O(无穷)，但是空间复杂度很小为O(1)。
2.队列法
首先我们出师一个[L,R]的一维数组，然后在[L,R]中随机一个下标作为新产生的随机数，然后将该随机数与下标为R的元素交换，然后再在[L,R-1]中随机新的随机数……以此递归，就可以在短时间内取到想要的随机数列。
这种方法的时间复杂度为O(m)，但是空间复杂度会达到O(n)。

Answer 7

直接random_shuffle就可以，
如果n特别大，可以直接随机，然后如果重复就重新随机。