CODEWITHSUNDEEP
c++random
James Leonard
James Leonard

Reputation: 3763

Generate a random number with no repeating digits?

I'd like to generate a random number with each digit being in range from 0-9 and not repeating itself. Assume finite length of 4.

How can this be done please?

Upvotes: 2

Views: 3302

Answers (3)

duncan
duncan

Reputation: 2433

If you'd rather avoid needless use of std::vector and the memory allocations it brings, excessive randomisation calls presumably used within random_shuffle, there's a simpler approach if you play with some math.

If you can count how many valid (i.e. acceptable) sequences exist, C, and you can devise a bijective function that maps from this counter to each valid sequence instance then things become trivial. Generate a random integer in the range [0,C), plug that into your function which returns the valid output.

If I understand your example correctly, you want to generate a random 4 digit sequence ABCD (representing an integer in the range [0,9999]) where digits A, B, C and D are different from one another.

There are 5040 such valid sequences: 10 * 9 * 8 * 7.

Given any integer in the range [0, 5039], the following function will return a valid sequence (i.e. one in which each digit is unique), represented as an integer:

int counter2sequence(int u) {
  int m = u/504;
  u %= 504;
  int h = u/56;
  u %= 56;
  int t = u/7;
  u %= 7;

  const int ih = h;
  const int it = t;

  if (ih >= m) ++h;
  if (it >= ih) ++t;
  if (t >= m) ++t;
  if (u >= it) ++u;
  if (u >= ih) ++u;
  if (u >= m) ++u;

  return ((m*10 + h)*10 + t)*10 + u;
}

E.g.

counter2sequence(0) => 0123
counter2sequence(5039) => 9876

Upvotes: 0

paddy
paddy

Reputation: 63481

I believe you are talking about generating permutations.

Try something like this:

int used[10] = {0};
int n = 0;
int number = 0;

while( n < 10 ) {
    int d = rand() % 10;
    if( used[d] ) continue;
    used[d] = 1;
    number = number * 10 + d;
    n++;
}

Not the most efficient... It simply tracks what digits have been used, and rerolls any time a used digit is encountered.

The above does have the side-effect that zero is technically not used if it's the first number chosen. You could explicitly prevent this, or simply accept that some numbers will be 9 digits long.

Upvotes: 0

Kos
Kos

Reputation: 72271

To generate the digits:

std::vector<int> vec = {0,1,2,3,4,5,6,7,8,9}; // or initialize from array if not c++11
std::random_shuffle(vec.begin(), vec.end());
vec.resize(4);

And to join the digits into a single number:

int number = 0;
for (auto i = vec.begin(); i != vec.end(); ++i) {
    number = 10 * number + (*i);
}

Upvotes: 6

Related Questions