random number generator without duplicate

[dkqnfl330]

I'm trying to generate random number without repeating same number...



#include<iostream>
#include<string>
#include<ctime>
#include<random>
using namespace std;
int ** gen2Array(int n);
void randomFillUnique(int **a, int n);

int main()
{
int n;
cout << "Enter a N number for size of the n x n array: ";
cin >> n;
cout << endl;
int** result = gen2Array(n);
randomFillUnique(result, n);
cout << "Generated array : " << endl;
for (int i = 0; i<n; i++)
{
for (int j = 0; j<n; j++)
{
cout << result[i][j] << "\t";
}
cout << endl;
}
system("pause");
return 0;
}
int ** gen2Array(int n)
{
int **p;
p = new int*[n];
for (int i = 0; i < n; ++i)
{
p[i] = new int[n];
}
return p;
}
void randomFillUnique(int **a, int n)
{
static default_random_engine e(static_cast<unsigned>(time(NULL)));
uniform_int_distribution<int> u(1, (100));

for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
a[i][j] = u(e);

}
}
}

[Golden Lizard]

Check if the number has already been used using an alternative data structure like a hash table, if the number has been generated before, generate another number and repeat if it has been used too.

[CroCo]

What is your problem?

[gunnerfunner]

OP: take a look here: http://stackoverflow.com/questions/25878202/generating-random-non-repeating-number-array-in-c

[alonso12]

Something like this.
This is in C++/Qt, adjust to your language.

    QList<uint> numList;
    uint num;
    bool duplicate;

    //generate your seed here

    for (uint i = 0; i < qty; i++)
    {
        do {
            num = (generate your random number);
            if (numList.contains(num))
            {
                duplicate = true; // skip duplicates
            }
            else
            {
                numList.append(num);
                duplicate = false;
            }
        } while (duplicate);
    }

[keskiverto]

Apart from the strategy, this issue too:

uniform_int_distribution<int> u( 1, 100 );

for (int i = 0; i < n; i++)
   for (int j = 0; j < n; j++)

There are 100 unique values in the distribution. n*n will be used. Therefore, n larger than 10 is not possible.


gunnerfunner's answer is the way to go here. First take enough unique values (imagine a "deck" of unique "cards"). Then pull values/cards from the deck. *However, a dealer does not draw a card randomly; dealer draws the first card from an already shuffled deck.

[Chervil]

A possibility, though it can be inefficient when the possible random numbers is similar to the number of values to be generated.

#include <ctime>
#include <random>
#include <unordered_set> 

void randomFillUnique(int **a, int n)
{
    static default_random_engine e(static_cast<unsigned>(time(NULL)));
    uniform_int_distribution<int> u(1, 100);

    size_t size = n * n;
    
    std::unordered_set<int> randoms;
        
    if (size > 100)
    {
        cout << "size " << size << " is too large\n";
        return;
    }
    
    while (randoms.size() < size)
    {
        randoms.insert( u(e) );
    }
    
    std::unordered_set<int>::iterator it = randoms.begin();
    
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            a[i][j] = *it++;
        }
    }
}

[boost lexical cast]

Like gunnerfunner said, shuffle an array/vector that has all the values 1-100.

<algorithm> ~ std::random_shuffle()

http://www.cplusplus.com/reference/algorithm/random_shuffle/

[keskiverto]

Note: the std::random_shuffle has already been deprecated, because it relies on deprecated rand. The OP is already using the new <random> and should thus choose the std::shuffle instead.

Another note about:

int ** gen2Array(int n)
{
  int **p;
  p = new int*[n];
  for (int i = 0; i < n; ++i)
  {
    p[i] = new int[n];
  }
  return p;
}

All values of the array may not be in consecutive memory. Consider this alternative:

int ** gen2Array(int n)
{
  int **p = new int*[n];
  p[0] = new int[n*n];
  for ( int row = 1; row < n; ++row )
  {
    p[row] = p[0] + n * row;
  }
  return p;
}

And then the obligatory big one: where are your deletes?