?? Non-Repeating Random Number Array ??

[Eristato]

Is there any way to create a number array that prints out 20 random numbers with no repeats? Could it be done starting with the code below?

#include<iostream>
#include<stdlib.h>
#include<time.h>
#include<math.h>
#include<vector>

using namespace std;

int main(){

    srand(time(NULL));


    int sizeofarray = 20;
    int nubersArray[sizeofarray];
    int ARRAY[sizeofarray] = {};

    for(int i = 0; i < sizeofarray; i++){
        nubersArray[i] = rand() % 100 + 1;
        cout << nubersArray[i] << " ";
    }
    cout << endl;
}

[dutch]

#include <iostream>
#include <cstdlib>
#include <ctime>

using namespace std;

int main() {
    srand(time(0));

    const int Size = 20;
    const int MaxNum = 40;

    int numbers[Size];
    bool used[MaxNum] = {};

    for (int i = 0; i < Size; ) {
        int r = rand() % MaxNum + 1;
        if (!used[r - 1]) {
            numbers[i++] = r;
            used[r - 1] = true;
        }
    }

    for (int i = 0; i < Size; ++i)
        cout << numbers[i] << ' ';
    cout << '\n';
}

[Eristato]

Thanks for the help, but is there a more basic way of doing this?? Possibly without bool?

[Ganado]

They are aren't going completely "random" numbers if you're forcing them to not repeat. That partially defeats the point of randomness.

There isn't one correct way to rule them all here.
(Edit: But I actually like dutch's answer, more than mine. It has linear complexity proportional to the size of the random pool. That's probably as good as you'll get.)

I'll go over some possibilities:

The short answer "yes", but time complexity to generate the next number that doesn't repeat grows significantly, because each time you generate a new number, you need to compare it against all other numbers to make sure it doesn't repeat.
As you get closer and closer to using up the majority of numbers in your pool, the chances of picking a new number become smaller and smaller.

But if the array is short, and the pool of random numbers is large enough, this isn't really a concern.

#include <iostream>
#include <cstdlib>
#include <ctime>

using namespace std;

// determines if an element is in the array of size n
bool contains(int arr[], int n, int element)
{
    for (int i = 0; i < n; i++)
    {
        if (arr[i] == element)
            return true;
    }
    return false;
}

int main(){

    srand(time(NULL));

    const int sizeofarray = 20;
    int numbersArray[sizeofarray];

    for (int i = 0; i < sizeofarray; i++)
    {
        int randnum = rand() % 100 + 1;
        while (contains(numbersArray, i, randnum))
        {
            // re-roll if we rolled a previously used number
            randnum = rand() % 100 + 1;
        }
        numbersArray[i] = randnum;
    }


    for (int i = 0; i < sizeofarray; i++)
    {
        cout << numbersArray[i] << " ";   
    }
    cout << '\n';
}

Another way of doing it is to generate numbers in a non-random or semi-random way, and then shuffle those numbers.

e.g.

#include <random>
#include <algorithm>
#include <iterator>
#include <iostream>

using std::cout;
 
int main()
{
    std::random_device rd;
    std::mt19937 gen(rd());
 
    const int sizeofarray = 20;
    int numbersArray[sizeofarray];

    for (int i = 0; i < sizeofarray; i++)
    {
        numbersArray[i] = i + 1;
    }
    
    // shuffle
    std::shuffle(numbersArray, numbersArray + sizeofarray, gen);

    for (int i = 0; i < sizeofarray; i++)
    {
        cout << numbersArray[i] << " ";   
    }
    cout << '\n';
}

PS: Arrays must have compile-time sizes, change your int sizeofarray] to const int sizeofarray.

There's other ways as well, all have different distributions or other slight differences. It really depends on what you want to use those numbers for. Why do they all need to be unique? Any proper method will probably equally complex or more complex than dutch's solution, do you actually have a reason for not liking his solution?

[Eristato]

For a part of a school project. Technically no use for the numbers. The program would print 20 numbers, randomly selected between 1-100, so picking a new number shouldn't be a problem. Thanks for the fixes, and that should be enough help. :)

[dhayden]

- Create an array from 1 to 100.
- Select a random index into the array and print the number at that position.
- Now swap that number with the number at the end of the array. By doing this, items 1-99 are still candidates to be printed.
- Now select a random index from 1 to 99. Print the item there and swap with item 99.
- Select item from 1 to 98. Print, swap.
- etc.

This doesn't use bools but it's basically the same process.

Another possibility:
Create the items 1-100 in an array
Shuffle the array
print the first 20 items.

This is a lot more work because you create 100 random numbers during the shuffle.

Finally, I seem to recall this problem showing up a year or two ago and someone pointed to an algorithm in Knuth that did something typically brilliant to solve the problem.