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

雷雷

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特別大，可以直接隨機，然後如果重複就重新隨機。