How to generate an array of random & unique integers in C?

Question

I am creating a C-prog that requires an array of 17 integers, all being less than 18 and unique. This is what I could do until now:

int ques_arr[17];
int x,y;
time_t t;
srand((unsigned)time(&t));

for(int a=0; a<17; a++)
{
x=rand()%18; //Assume that srand() has been declared in the program
 for(int aa=0; aa<17; aa++)
 {
  if(x==ques_arr[aa])
   { do{
        y=0;
        y=rand()%18;
        }while(y==ques_arr[aa]);
      x=y; 
      ques_arr[a]=x;
    }else ques_arr[a]=x;
  }
}

My current algorithm is that everytime rand() generates a number, that number will be checked throughout array whether same number already exists or not, if it does, rand() keeps on generating a number until a unique number is obtained and then it is stored in the array.If such a number doesn't exist in the array, it's directly fed in to it.

As of now, numbers stored in the array are not unique.

Any help would be appreciated.

[Fisher–Yates shuffle](https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle) — dbush, Jun 13 '20 at 04:54
For future reference: "//Assume that srand() has been declared in the program" does not make this a proper [mcve]. Please take the [tour] and read [ask]. — jwdonahue, Jun 13 '20 at 05:03
@jwdonahue that comment was just to indicate that srand() is being used for this program, this was for those who might come up with "try using srand()". Although I've changed that — Ayush Nanglia, Jun 13 '20 at 05:21
@AyushNanglia, okay, so you din't understand my gist there. I was implying that you needed to post an [mcve]. You code comment implied that you had not done so. But you seem to have gotten an answer anway. It might help others who come across this thread in the future, if you posted an actual [mcve]. — jwdonahue, Jun 13 '20 at 07:29

David Ranieri · Accepted Answer · 2020-06-13T06:00:56.577

0

This is not an optimal solution, your time complexity once you have fixed the problem in your code is O(n²), you can reduce the time complexity to O(n) using the "Knuth Shuffle algorithm":

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#include <time.h>

static int rrand(int value)
{
    return (int)((double)value * (rand() / (RAND_MAX + 1.0)));
}

static void randomize(int arr[], int size)
{
    for (int idx = 0; idx < size; idx++)
    {
        arr[idx] = idx;
    }
    for (int idx = size; idx > 1; idx--)
    {
        int num = rrand(idx);
        int tmp = arr[idx - 1];

        arr[idx - 1] = arr[num];
        arr[num] = tmp;
    }
}

int main(void)
{
    srand((unsigned)time(NULL));

    int arr[17] = {0};
    int size = sizeof arr / sizeof *arr;

    randomize(arr, size);
    for (int idx = 0; idx < size; idx++)
    {
        printf("%d\n", arr[idx]);
    }
    return 0;
}

edited Jun 13 '20 at 06:00

answered Jun 13 '20 at 05:23

David Ranieri

39,972
7
52
94

You should add a caveat about `rand() % size` since 1. It will generate numbers with a non-uniform distribution, 2. `rand()`'s least-significant bits are notoriously bad. – jamesdlin Jun 13 '20 at 05:30
@jamesdlin oope, I don't know why I added this `--`, edited, thanks – David Ranieri Jun 13 '20 at 05:36
I meant that using `%` to get random numbers in a specific range is an anti-pattern. – jamesdlin Jun 13 '20 at 05:56
@jamesdlin: "`rand()`'s least-significant bits are notoriously bad" .... you might lke to read https://stackoverflow.com/questions/61411498/why-does-rand-repeat-numbers-far-more-often-on-linux-than-mac – pmg Jun 13 '20 at 06:18

How to generate an array of random & unique integers in C?

1 Answers1