CODEWITHSUNDEEP
c++arraysmatrix
Jame
Jame

Reputation: 3854

Generate random number in range without repetition

I am using C++ to generate n uniform numbers in a given range without repeatition. I want to save it in array(not vector). I found a code but it does not allow to generate number without repetition. 

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);

For example, I will generate 5 random numbers in range 0-9 such as

1 0 3 8 6

This is my code

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 ;
}

Second way, I used the code bellow which allows without repetition. But it is not support in g++ (I am using g++ in 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";
}

Upvotes: 2

Views: 2522

Answers (3)

ChrisD
ChrisD

Reputation: 674

The easiest way to achieve what you want is to do what user Untitled123 suggested (see below). To compile: 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;
}

Upvotes: 1

adjan
adjan

Reputation: 13652

Use the Fisher-Yates shuffle algorithm to shuffle a vector/array filled with all the numbers in the desired range: https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle

Upvotes: 1

Untitled123
Untitled123

Reputation: 1293

There's a couple ways you can do this.

  1. If the random number is already in the array, then generate another one until you find a number that has not been seen before. This is quick to implement but has the disadvantage of very high running time theoretically.

  2. Create the entire range to begin with in an array and then scramble it. To get k numbers, obtain the first k elements of the scrambled array.

Upvotes: 2

Related Questions