Generate random but non-repeating numbers (C++)

Question

I want to generate a set of non-repeating random numbers from 0...n.

e.g: [9,2,5,7,4,6,1,3,8,0]

My current method is generating random numbers in a while loop until the std::set count is n. Obviously this takes quite a while to finish for large sets. Is there a better way to do this?

It looks to me like you want to shuffle a sequence `[1,n]` :-) http://stackoverflow.com/questions/6926433/how-to-shuffle-a-stdvector-in-c — cnicutar, Jun 08 '12 at 20:47
@cnicutar: sunofa... now I feel silly... you are absolutely right! :) if you put that as the answer, I will checkmark it! — Samaursa, Jun 08 '12 at 20:48
It's OK. Why don't you answer your own question with a nice C++ idiomatic example of doing this ? — cnicutar, Jun 08 '12 at 20:50
If the number of numbers and the range of the numbers isn't identical, see [Floyd's sampling algorithm](http://stackoverflow.com/a/2394292/179910). — Jerry Coffin, Jun 08 '12 at 20:53
possible duplicate of [Non-repeating random number generator](http://stackoverflow.com/questions/5382037/non-repeating-random-number-generator) — Mooing Duck, Jun 08 '12 at 22:59

score 3 · Accepted Answer · answered Jun 08 '12 at 20:49

3

You can place the sequential values in a STL collection, and then use random_shuffle to shuffle them appropriately.

answered Jun 08 '12 at 20:49

Reed Copsey

554,122
78
1,158
1,373

score 1 · Answer 2 · edited Jun 08 '12 at 22:16

1

Shuffle and iterate your list of numbers.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    vector<int> v;


    for(int i=0;i<10;i++)
        v.push_back(i);

    random_shuffle(v.begin(), v.end());

    for(vector<int>::iterator itr=v.begin(); itr != v.end(); ++itr)
        cout << *itr << endl;


}

edited Jun 08 '12 at 22:16

cdhowie

158,093
24
286
300

answered Jun 08 '12 at 21:03

kjp

3,086
22
30

score 1 · Answer 3 · answered Jun 08 '12 at 21:27

generating a sequence and shuffling may be what you want, however its not necessarily the same as generating random numbers and discarding ones that have occurred before. For example, if you want 10 unique random numbers from between 1 and 2 million you obviously won't get the desired distribution by just generating

1,000,000
1,000,001
1,000,002
1,000,003
1,000,004
1,000,005
1,000,006
1,000,007
1,000,008
1,000,009

and shuffling those.

You could instead generate random numbers from the desired range until you have the number desired, then sort and unique the results, and then generate enough additional random number to make up whatever was eliminated by the uniquing (ensuring the new numbers are unique as you go). If the range of generated numbers isn't that much larger than the number of values you want then you might just generate some extra values to start off with. In any case the final step once you have the desired number of unique values, is to shuffle them so they are not in sorted order.

RelaxedMind · Answer 4 · 2016-05-20T12:13:52.733

Have a try.

#include <iostream>
#include <algorithm>
using namespace std;
void main()
{


    int *tab;
    int nr;
    srand(time(0));

    cout << "How many numbers do you want to generate?:  ";
    cin >> nr;

    tab = new int[nr]; //Dynamic memory allocation


    for (int i = 0;i < nr;i++)
        tab[i] = i+1;
    random_shuffle(&tab[0], &tab[nr]); //Shuffle the numbers from tab;

    cout << "\t\tMixed numbers are: " << endl;
    for (int i = 0;i < nr;i++)
        cout << "Number [" << i + 1 << "]: " << tab[i]<<endl;



    delete [] tab;
    cin.get();

Generate random but non-repeating numbers (C++)

4 Answers4