1,105,242 Community Members

Generating Random Numbers Without Repeats

Member Avatar
Reputation Points: 2,218 [?]
Q&As Helped to Solve: 768 [?]
Skill Endorsements: 26 [?]
 
0
 

Very often you find that you need to generate an array of integers where each integer is unique. The program below contains two functions that do that in different ways. One uses a boolean array to keep track of the numbers that have been generated. If a number has already been generated, more numbers are generated until you get one that hasn't been generated yet, thus guaranteeing no repeats.

The other method is more complex and involves a tree. The rand () function is called fewer times with this method. This method tends to be faster when generating large arrays of numbers.

/* This program demonstrates two different techniques of creating random
   integers without duplicates.  The first technique is a tree-based method
   designed to minimize the number of calls to the rand () function.  It is
   a tree based algorithm and is well suited when calls to rand () are
   computationally expensive or when there is a very large number of
   random numbers to generated.
   
   The second technique is simpler and uses a boolean array to keep track of what
   numbers have been selected already.  If a random number is generated that has
   occurred before, a new one is generated.  With very large arrays, there will be
   a lot of repeat random number generation, so the first technique tends to be more
   efficient for large sets, though the timings of the two techniques are much closer
   than I anticipated.  I had expected the first technique to vastly outperform the
   second on tasks like generating generating all numbers from 1 to 20,000 exactly once,
   but that doesn't appear to be the case.
   
   The example below is a much smaller example, shuffling playing cards, so you are only
   dealing with 52 numbers.
*/

#include <iostream>
#include <string>
#include <ctime>
#include <iomanip>
using namespace std;

struct node
{
    int value;    // radomly produced integer value
    node* left;   // pointer to right child
    node* right;  // pointer to left child
    int leftSize; // yourself + number of descendants in left tree
                  // keep track of this so you don't have to keep
                  // recalculating by traversing
};

void GenerateRandomIntegers1 (int min, int max, int* array, int arraySize);
void GenerateRandomIntegers2 (int min, int max, int* array, int arraySize);
void Display (int array[], int arraySize);


string card[] = {"Ace", "2", "3", "4", "5", "6", "7", "8", "9", "10",
                 "Jack", "Queen", "King"};
string suit[] = {"Spades", "Hearts", "Clubs", "Diamonds"};


int main ()
{
    srand (time (NULL));
    
    int min = 0;
    int max = 51;
    int arraySize = max - min + 1;
    int* array = new int[arraySize];
    
    cout << "First method - Shuffle\n\n";
    GenerateRandomIntegers1 (min, max, array, arraySize);    
    Display (array, arraySize);
    cout << "\n\nSecond method - Shuffle\n\n";
    GenerateRandomIntegers2 (min, max, array, arraySize);    
    Display (array, arraySize);

    cin.get ();  // pause screen    
    return 0;
}


void GenerateRandomIntegers1 (int min, int max, int array[], int arraySize)
// a tree-oriented method.  Random numbers never have to be regenerated.  Random
// number is generated out of a range of the number of empty slots remaining.
// If the number 3 is generated, the number selected will be 4th smallest
// (add 1 to 3 since 0 is smallest) as-of-yet-unpicked number.
// node->leftSize is the number of nodes less than that node that are children
// have been picked already (includes itself).  This is needed in order to know
// how much to adjust a random number. 
{     
     node* tempNodes = new node[arraySize];
     node* headNode = &tempNodes[0];
     int range = max - min + 1;
     headNode->value = rand () % range + min;
     headNode->left = NULL;
     headNode->right = NULL;
     headNode->leftSize = 1;
     
     array[0] = headNode->value;  // pick first/top node
     node* treeTop;
     node* nodeToInsert;
     bool inserted;     
     
     for (int i = 1; i < arraySize; i++)
     {
         range--;  // decrement random number range each time since one fewer
                   // value is available.
         tempNodes[i].leftSize = 1;
         tempNodes[i].left = NULL;
         tempNodes[i].right = NULL;
         int positionAmongUnpicked = rand () % range;
         // insert at positionAmongUnpicked spot in list of unpicked numbers.
         // (i.e. if remaining unpicked numbers are {6, 12, 14, 17, 20} and
         // positionAmongUnpicked is 3, the value will end up being 17).
         tempNodes[i].value = positionAmongUnpicked + min; 
         inserted = false;
         treeTop = headNode;
         nodeToInsert = &tempNodes[i];
         
         // insert node
         do
         {
             if (nodeToInsert->value + treeTop->leftSize > treeTop->value)
             // check whether to insert right or left
             {
                  // go right.  There are treeTop->leftSize smaller nodes already,
                  // so increment by that number.
                  nodeToInsert->value = nodeToInsert->value + treeTop->leftSize; 
                  if (treeTop->right == NULL)
                  {
                       treeTop->right = nodeToInsert;
                       inserted = true;
                  }
                  else
                      treeTop = treeTop->right;
             }
             else
             {
                 // go left
                 treeTop->leftSize++;
                 if (treeTop->left == NULL)
                 {
                      treeTop->left = nodeToInsert;
                      inserted = true;
                 }                
                 else
                      treeTop = treeTop->left;                
             }             
         }
         while (!inserted);
         
         array[i] = nodeToInsert->value; 
     } 
     
     delete []tempNodes; // clean by deleting nodes.
}


void GenerateRandomIntegers2 (int min, int max, int array[], int arraySize)
// this method will generate repeated random numbers.  boolean array
// keeps track of what numbers have been picked.  Generates another if
// this number has already been picked.
{
     int range = max - min + 1;
     bool* picked =  new bool[range];
     // initialize all to unpicked
     for (int i = 0; i < range; i++)
         picked[i] = false;
         
     int value;
     
     for (int i = 0; i < arraySize; i++)
     {
         value = rand () % range;
         if (picked[value])
             i--;  // already picked.  for-loop increments, so decrement here
         else
         {
             array[i] = value + min;
             picked[value] = true; // hasn't been picked yet.  Assign to array,
                                   // flag as picked.
         }
     }
     
     delete [] picked; // clean up. delete boolean array
}


void Display (int array[], int arraySize)
{
     for (int i = 0; i < arraySize; i++)
     {
         cout << left << setw(6) << card[array[i] % 13] << " of " <<
                 suit[array[i] % 4] << endl;
     }
}
Member Avatar
VernonDozier
Posting Expert
5,632 posts since Jan 2008
Reputation Points: 2,218 [?]
Q&As Helped to Solve: 768 [?]
Skill Endorsements: 26 [?]
Featured
 
0
 

I have changed the Display function from this:

void Display (int array[], int arraySize)
{
     for (int i = 0; i < arraySize; i++)
     {
         cout << left << setw(6) << card[array[i] % 13] << " of " <<
                 suit[array[i] % 4] << endl;
     }
}

to this:

void Display (int array[], int arraySize)
{
     for (int i = 0; i < arraySize; i++)
     {
         cout << left << setw(6) << card[array[i] % 13] << " of " <<
                 suit[array[i] / 13] << endl;
     }
}

because I think it's easier to see the mappings from 0 to 51 to the cards themselves and more generalizable. Using the mod (%) operator as I did before works because 4 and 13 are relatively prime. However if you had, say, 4 card values and 2 suits instead of 13 and 4, if you used the mod (%) operator to extract both the card and suit, you could get duplicate cards from different integer values since 2 and 4 are not relatively prime. Using the divide (/) and mod (%) operators allows you not to worry about relative primality.


[EDIT]
Hmm. I'm not sure exactly how to edit the original code snippet itself to make the change above. Maybe it's not possible and you can only add comments. If so, please read the comment above. The code snippet above will work in either case, but again, using the / and % operators is probably better for readability, plus the card mappings will be less scattered (i.e. all Hearts are next to each other).
[/EDIT]

You
Post:
Start New Discussion
Tags Related to this Article