Генерировать случайное число в диапазоне без повторения

Question

Я использую C++ для генерации n равномерных чисел в заданном диапазоне без повторения. Я хочу сохранить его в массиве (а не в векторе). Я нашел код, но он не позволяет генерировать число без повторения.

std::random_device rd;  // only used once to initialise (seed) engine 
std::mt19937 rng(rd()); // random-number engine used (Mersenne-Twister in this case) 

std::uniform_int_distribution<int> uni(0,10-1); // guaranteed unbiased 
auto random_integer = uni(rng); 

Например, я генерировать 5 случайных чисел в диапазоне 0-9, таких как

1 0 3 8 6 

Это мой код

typedef unsigned int U32, *PU32; 
U32 total_num = 5; 
U32 *rndArray = new U32[total_num]; 
for (U32 i = 0; i < total_num; i++) 
{ 
    std::random_device rd // only used once to initialise (seed) engine 
    std::mt19937 rng(rd());  
    std::uniform_int_distribution<int> uni(0,10-1); 
    auto random_integer = uni(rng); 
    rndArray[i] = random_integer ; 
} 

Второй способ, я использовал код, приведенную ниже, который позволяет без повторения. Но это не поддержка в g ++ (я использую g ++ в ubuntu)

#include <random> 
#include <algorithm> 
#include <iterator> 
#include <iostream> 
typedef unsigned int U32; 
int main() 
{   
    U32 total_num = 5; 
    U32 *rndArray = new U32[total_num]; 
    std::random_device rd; 
    std::mt19937 g(rd()); 
    std::vector<int> v = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}; 
    std::shuffle(v.begin(), v.end(), g); 
    for (int i=0;i<5;i++) 
    { 
     rndArray[i]=v[i]; 
     std::cout<< rndArray[i] << " "; 
    } 

    std::cout << "\n"; 
} 

Answer 1

Есть несколько способов, которыми вы можете это сделать.

1. Если случайное число уже находится в массиве, то сгенерируйте еще один, пока не найдете число, которое раньше не было. Это быстро реализуется, но имеет недостаток в очень высоком времени работы теоретически.

2. Создайте весь диапазон, чтобы начать с массива, а затем скремблируйте его. Чтобы получить k чисел, получите первые k элементов скремблированного массива.

Answer 2

Используйте алгоритм перетасовки Fisher-Yates перетасовать вектор/массив, заполненный всеми числами в требуемом диапазоне: https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle

Answer 3

Самый простой способ добиться того, что вы хотите, чтобы делать то, что пользователь Untitled123 (см. Ниже). Для компиляции: g ++ -std = C++ 11 file.cpp

#include <vector> 
#include <algorithm> 
using namespace std; 

int randomize(const int &i) return rand() % i; 

int main() { 
    srand(unsigned(time(0))); 

    int n = 10; 

    vector<int> sample(n); 
    // generate numbers 0 .. n-1 
    iota(sample.begin(), sample.end(), 0); 
    // shuffle elements 
    random_shuffle(sample.begin(), sample.end(), randomize); 
    // grab the first five elements after shuffling 
    vector<int> chosen(sample.begin(), sample.begin() + 5); 

    // do stuff 

    return 0; 
}