Printing 5 Non-Duplicate Random Numbers

[jsanti2519]

Hello everyone. I am trying to print out a set of unique random integers in an array (e.g. 1 4 2 3 0). An example of what would not work is 1 3 1 4 0 where 1 repeats itself.

I tried to run this code and the code did not process successfully. What modifications do I need to have on my current code? I appreciate the help everyone.

#include <iostream>
#include <ctime>
#include <cstdlib>
using namespace std;

void arrayFunction(int a[], int b);

int main() {
    int arr[5];
    arrayFunction(arr, 5);
    
    return 0;
}


void arrayFunction(int a[], int b) {
    srand(time(NULL));
    for(int i = 0; i < b; ++i) {
        a[i] = i; //sets values for a[] consecutively.
    }


    int randStorage[b];
    for(int j = 0; j < b; ++j) {
        bool isUnique = false; //we assume that there is no unique number yet.
        while(!isUnique) {
            randStorage[j] = a[rand() % b];
            for(int k = 0; k < j; ++k) {
                if(randStorage[k] == randStorage[j]) isUnique = false;
            }
        }
    }
    for(int print = 0; print < b; ++print) cout << randStorage[print] << " ";
}

[Duthomhas]

Refactor. Your code tries to do too many things at once.

(1)
Keep track of how many items are in your array.

int main() {
    const int MAX_ARR_SIZE = 5;
    int arr[MAX_ARR_SIZE];
    int arr_size = 0;

Whenever you add an element to the array, simply increment the arr_size. Don’t let arr_size ever become larger than MAX_ARR_SIZE.

(2)
You should have a function that determines whether or not a number is currently stored in the array. You could call it "is_element_of" or something:

bool is_element_of( int x, int xs[], int size )

This is where you run through the array and test for uniqueness.
Hint: you do not need a variable “isUnique” for this.
(Good job for the good variable name, though.)

Hint2: “b” is a terrible variable name for a size/count/non-random,unpaired integer.

Hint3: You do not need an additional array.

(3)
Populate the array. Pull random numbers until arr_size == MAX_ARR_SIZE.

Only add elements to the array iff the random value you get is not already in the array.

(4)
Congratulations, you have a randomly-populated array of arr_size == MAX_ARR_SIZE elements.

Print them.


Hope this helps.

[keskiverto]

That approach has a conceptual problem. The further you go, the less likely it becomes to get a unique value.
The first pick is always unique.
The second pick has 80% chance. The is one value that you cannot accept.
The fifth/last pick has only 20% chance. Therefore, you might have to try multiple times before you hit the one and only unused value.

Think of a deck of cards. Every card is unique. If you shuffle the deck, then the cards are in random order.
http://www.cplusplus.com/reference/algorithm/shuffle/

// shuffle algorithm example
#include <iostream>     // std::cout
#include <algorithm>    // std::shuffle
#include <array>        // std::array
#include <random>       // std::mt19937
#include <chrono>       // std::chrono::system_clock
#include <numeric>      // std::iota

int main () {
  std::array<int,5> foo {};
  std::iota( foo.begin(), foo.end(), 0 );

  unsigned seed = std::chrono::system_clock::now().time_since_epoch().count();

  shuffle( foo.begin(), foo.end(), std::mt19937(seed) );

  std::cout << "shuffled elements:";
  for ( int& x: foo ) std::cout << ' ' << x;
  std::cout << '\n';
}

[lastchance]

#include <iostream>
#include <set>
#include <vector>
#include <ctime>
#include <cstdlib>
using namespace std;


set<int> ordered( int N, int imaxp1 )
{
   set<int> S;
   while( S.size() < N ) S.insert( rand() % imaxp1 );
   return S;
}


vector<int> unordered( int N, int imaxp1 )
{
   vector<int> V;
   for ( set<int> S; S.size() < N; )
   {
      int i = rand() % imaxp1;
      if ( S.insert( i ).second ) V.push_back( i );
   }
   return V;
}


int main()
{
   srand( time( 0 ) );
   const int N = 5, imaxp1 = 10;
   cout << "\nOrdered selection:   ";   for ( int i : ordered  ( N, imaxp1 ) ) cout << i << " ";
   cout << "\nUnordered selection: ";   for ( int i : unordered( N, imaxp1 ) ) cout << i << " ";
}

Ordered selection:   0 1 6 7 9 
Unordered selection: 3 6 1 8 2  

[lastchance]

#include <iostream>
#include <algorithm>
#include <numeric>
#include <vector>
#include <ctime>
#include <cstdlib>
using namespace std;


vector<int> partial_shuffle( int N, int imaxp1 )
{
   vector<int> V( imaxp1 );
   iota( V.begin(), V.end(), 0 );
   for ( int n = 0; n < N; n++ ) swap( V[n], V[n + rand() % ( imaxp1 - n )] );
   V.resize( N );
   return V;
}


int main()
{
   srand( time( 0 ) );
   const int N = 5, imaxp1 = 10;
   for ( int i : partial_shuffle( N, imaxp1 ) ) cout << i << " ";
}

Having a partial_shuffle() would be quite nice in the standard library.

[Duthomhas]

Out of 32767 possible values, your chances of collision are:

1st pull: 0/32767
2nd pull: 1/32767
3rd pull: 2/32767
4th pull: 3/32767
5th pull: 4/32767

I think that is pretty good chances.

If you want to restrict the choices to a smaller subset, then yes, you will have a more likely possibility of collisions.

Given five numbers that can be pulled (like {0,1,2,3,4}):

5th pull: 4/5 → you may need to pull up to five times (on average) to get the remaining unused value.

This will happen in less time than it takes for you to blink. Still not a problem.


[edit]
BTW, simply executing another pull is not a conceptual error. It is exactly what is recommended you do when constraining your output range when you pull a value outside that range. It is also the correct way to handle the error.

Of course, some care must be taken to prevent stupid if selecting n ≪ N available items.

[lastchance]

If you choose 5 numbers from 5 with a reject-if-seen-before approach then it will take, on average, 137/12, or nearly 11.5 "pulls" and a lot of checks. If you use a shuffling type of approach then it will take 5 "pulls" and there is no need for any checks. So, for TIME, a shuffling approach is best.

On the other hand, a shuffling approach will require enough memory to store the whole sample space, so, for MEMORY, a reject-if-seen-before approach would consume less.

So ... there exist swings and roundabouts!