Weird pattern when I try to generate a 4-digit integer for which every digit is distinct

Question

When I try to write a small program in C language that is intended to generate a 4-digit integer for which every digit is distinct and nonzero, the returned value is always in pattern like 1abc: the first digit seems to always be 1, and sometimes the returned value will be more than 4-digit like 56127254. Could anyone help me look into this? Thank you very much in advance.

So basically the program includes two functions, int isvalid(int n) and int choose_N(void).

isValid return 1 if the integer consists of exactly 4 decimal digits, and all these digits are nonzero and distinct, and 0 otherwise.

And int choose_N(void) generates an integer that is 4-digit and all the digits are distinct and nonzero.

Here is my code:

#define N_DIGITS 4

....
....//the main function 

int isvalid(int n){
  int i, x; int check[N_DIGITS]={0};
  for(i=1;i<=N_DIGITS;i++){ //check whether all digits are nonzero
    if((check[i-1]=n%10)==0){
      return 0;
    }
    n /= 10;
  }
  for(i=0;i<N_DIGITS-1;i++){ // check whether all digits are distinct
    for(x=i+1;x<N_DIGITS;x++){
      if(check[i]==check[x])
        return 0;
    }
  }
  return 1;
}

int choose_N(void){
  int i; int number=0;
  while(!isvalid(number)){
    for(i=0;i<N_DIGITS;i++){
      srand(time(0));
      number += ((10^i)*(rand()%10));
    }
  }
  return number;
}

For srand(time(0));, I have tried various alternatives like srand(time(0)+i); or put this statement out of while loop, but those attempts seemingly did not work and still the returned value of choose_Nstill showed the werid pattern that I described.

Sorry, I just forgot to write that `N_DIGITS` is a constant integer 4. I have edited. — , Nov 22 '17 at 12:15
Don't call `srand` more than once. https://stackoverflow.com/questions/7343833/srand-why-call-it-only-once — Klas Lindbäck, Nov 22 '17 at 12:18

Jean-François Fabre · Accepted Answer · 2017-11-22T12:25:06.373

1

your choose_N method has several issues:

First, if the number isn't valid, you're not resetting it to 0, so it just grows and grows.
Second, srand(time(0)) is not necessary within the loop (and could yield the same result for several iterations), just do it at program start (srand() — why call it only once?)
Third and biggest mistake: 10 ^ i is 10 xor i, not 10**i. You can use an aux value and multiply by 10 in your loop. Since number of digits is low, no risk of overflow
minor remark: you want to pass in the loop at least once, so use a do/while construct instead, so you don't have to force the first while test.

I'm trying to fix your code:

int choose_N(void){
  int i, number;
  do
  {
    number = 0;
    int p = 1;
    for(i=0;i<N_DIGITS;i++)
    {      
      number += p*(rand()%10);
      p *= 10;
    }
  } while(!isvalid(number));

  return number;
}

edited Nov 22 '17 at 12:25

answered Nov 22 '17 at 12:18

Jean-François Fabre

137,073
23
153
219

Thank you very much for the detailed answers^_^! Just a further small question: as I fixed the function and tried to test the new returned value, it seemed that those returned value now usually, if not always, started with 1, 8, 2,3 and digit like 4, 5, 6 seldom appeared in the first place. Is it because that the computer cannot really generate the so-called random number as we wished? So what we can do is try to make the program generate the digits as random as possible. – Nov 22 '17 at 12:40
since random is _really_ random now, I cannot really answer. try removing the `srand` to get the same sequence, always, just to test. – Jean-François Fabre Nov 22 '17 at 12:42

score 0 · Answer 2 · answered Nov 22 '17 at 20:55

While @Jean-François-Fabre answer is the right one, it is not optimal algorithm. Optimal algorithm in such case would be using FIsher-Yates-Knuth shuffle and Durstenfeld's implementation.

Shuffling right array will produce numbers which are automatically valid, basically no need for isvalid(n) anymore.

Code

// Swap selected by index digit and last one. Return last one
int
swap_array(int digits[], int idx, int last) {
    if (idx != last) { // do actual swap
        int tmp = digits[last];
        digits[last] = digits[idx];
        digits[idx]  = tmp;
    }

    return digits[last];
}

int
choose_N_Fisher_Yates_Knuth() {
    int digits[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };

    int r = 0;
    for (int k = 0; k != N_DIGITS; ++k) {
        int idx = rand() % (9 - k);

        int n = swap_array(digits, idx, (9 - k) - 1);
        r = r * 10 + n;
    }
    return r;
}

int
main() {
    srand(12345);

    int r, v;

    r = choose_N_Fisher_Yates_Knuth();
    v = isvalid(r);
    printf("%d   %d\n", r, v);

    r = choose_N_Fisher_Yates_Knuth();
    v = isvalid(r);
    printf("%d   %d\n", r, v);

    r = choose_N_Fisher_Yates_Knuth();
    v = isvalid(r);
    printf("%d   %d\n", r, v);

    r = choose_N_Fisher_Yates_Knuth();
    v = isvalid(r);
    printf("%d   %d\n", r, v);

    return 0;
}

Output

Weird pattern when I try to generate a 4-digit integer for which every digit is distinct

2 Answers2