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

Question

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

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

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

Answer 1

After shuffling the n numbers, take the first m.
See Fisher-Yates.

Optimization: Use Fisher-Yates algorithm to determine the first m numbers.

Answer 2

Use shuffle (C++11, C++14) or random_shuffle (C++98) to randomly sort the array containing 1 to n, just pick the first m.

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

The following code requires a compiler that supports C++11 to compile.

#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

I basically don’t know C++, but I have two ideas:

1. After getting a random number, record it (for example, you can use hashmap in java to record it), and then the next time you go to the random number, if it has been fetched, fetch it again until it succeeds. However, the disadvantage of this method is that if the number of random numbers to be taken is relatively large, the efficiency is low.

2. An int array 1-25 (array subscript range), take a random number, if the random number is not the last number, move the obtained number to the last digit of the array, and then take 1- for the second time 24 (array subscript range), the fetched one is moved to the last digit. . . . . Just keep iterating in sequence.

Answer 4

An algorithm on csdn

Answer 5

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

Answer 6

There are two general methods:
1. Repeat and then randomize
This method is to first randomly select a number in [L, R]. If this number has been taken before, then repeat the process until a different number is obtained.
However, when this method selects m random numbers from n (m is close to n), the time complexity will be very large.
The worst-case time complexity of this method is O(infinity), but the space complexity is as small as O(1).
2. Queue method
First, we create a one-dimensional array of [L, R], then randomly add a subscript in [L, R] as a newly generated random number, then exchange the random number with the element with the subscript R, and then Randomly new random numbers in [L, R-1]... Using this recursion, you can get the desired random number sequence in a short time.
The time complexity of this method is O(m), but the space complexity will reach O(n).

Answer 7

Just random_shuffle,
If n is particularly large, you can directly randomize, and then re-randomize if it is repeated.