Member Avatar for gretty

hello

How do I ensure that the same number does not appear more than once in my random number creator?

Eg of output currently:

array = {30, 2, 12, 9, 2}; // has repeats

Eg of what I am trying to do:

array = {30, 2, 12, 9, 7}; // no repeated numbers

void generate_post::random(int array[], int max) {

	srand(time(NULL));

	for (int i = 0; i < 6; i++)
	{
		array[i] = (rand()%max)+1;
	}
}
  • 4 Contributors
  • 5 Replies
  • 115 Views
  • 8 Hours Discussion Span
  • Latest Post Latest Post by wildgoose

Dani AI

Generated

For : the easiest reliable way is to generate a pool of all possible values, shuffle it, and take the first N values. That avoids re-trying on collisions and scales predictably as N grows. Check first that the requested count does not exceed max, and do not seed the RNG inside the function (seeding every call with time() is what causes repeated sequences when called quickly).

A concise C++11+ implementation uses a pool + std::shuffle with a single std::mt19937 seeded once:

#include <vector>
#include <numeric>   // iota
#include <random>
#include <algorithm>

void generate_unique(int out[], int count, int max)
{
    if (count > max) throw std::invalid_argument("count > max");
    std::vector<int> pool(max);
    std::iota(pool.begin(), pool.end(), 1); // 1..max

    static std::random_device rd;
    static std::mt19937 gen(rd()); // seed once
    std::shuffle(pool.begin(), pool.end(), gen);

    for (int i = 0; i < count; ++i) out[i] = pool[i];
}

If max is huge and memory matters, use a rejection-with-set approach (generate randoms with std::uniform_int_distribution, insert into an unordered_set, repeat until you have enough). That mirrors ’s idea but uses uniform_int_distribution to avoid modulo bias. For very large sparse ranges a compact bitset / bitmap (as suggested) can be memory-efficient.

Further reading: std::shuffle for Fisher–Yates style shuffling () and std::uniform_int_distribution for unbiased integer sampling (cppreference).

Recommended Answers

All 5 Replies

Member Avatar for cgeier

Store the random number in a variable. Then search the array for the randomly generated number. If it is found, generate another random number. Repeat until random number does not exist in the array.

Member Avatar for mrnutty

Create an array;
From 'i' to 'SIZE' store 'i' into array.
shuffle array;

extract info from array into new one, without the same index
repeating.

commented: nice solution +2
Member Avatar for gretty

Create an array;
From 'i' to 'SIZE' store 'i' into array.
shuffle array;

extract info from array into new one, without the same index
repeating.

Would you be able to show me g=how to do this in code, I'm a bit confused :P

Would this work?

void generate_post::random(int array[], int max) {

	int n;
	srand(time(NULL));

	for (int i = 0; i < 6; i++)
	{
		n = (rand()%max)+1;
		for (int j=0; j<=i; j++) {
			if (array[j] != n)
				array[i] = n;
		}
	}
}
Member Avatar for mrnutty

something like this(not tested) :

void genRan(int array[], int sz)
{ 
   int *tmp = new int[sz];
   for(int i = 0; i < sz; i++)
         tmp[i] = i;

    //pick randome index from tmp, check if its a unique index
    // if so then populate array with the content from tmp.
  
   delete [] tmp;
}
Member Avatar for wildgoose

You aren't keeping a tally, only existance of a number so how about using a bit array.

65,536 numbers 0x10000 range from 0 to 65,535.
So technically you only need one bit per number. So let's assume you have 32-bit integers. Then 0x10000 / 0x0020 = 2048 slots, 32-bits each.
So

#define MAX_BIT  2048
 unsigned int bary[ MAX_BIT ];

void ClrAry( void )
{
   for (int i = 0; i < MAX_BIT; i++ )
        bary[i] = 0;
}

void SetBit( unsigned int nBit )
{
    bary[ nBit >> 5 ] |= 1 << (nBit & 0x1f);
}

bool GetBit( unsigned int nBit )
{
   unsigned int n;
    n = bary[ nBit >> 5 ];
    return (bool)(( n >> (nBit & 0x1f)) & 1);
}
Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.