Fill vector with random unique integers from a fixed pool of numbers

Question

I want to fill a vector with random integers but there can't be duplicates in it.

First off, I have this code to put numberOfSlots random integers between 0 and 7 in the vector (numberOfSlots can be 2 to 20):

srand((unsigned int)time(NULL));
unsigned int min = 0;
unsigned int max = 7;
std::vector<unsigned int> v;

for (int i = 0; i < numberOfSlots; i++) {
  unsigned int rdm = std::rand() % (max - min + 1) + min;
  v.push_back(rdm);
}

This is the code for when duplicate integers are allowed. This is working fine!

Now I want to the change that code so that from the same random pool of possible integers (min to max) the generated random integer is only added if it's not already in the vector.

So if for example numberOfSlots is 5, then the vector will have 5 entries that were randomly chosen from the pool but are not the same, e.g. 7, 1, 3, 5, 0. If numberOfSlots is 8, the vector will be for example 3, 1, 2, 7, 6, 0, 4, 5.

I know how to shuffle the vector and stuff but I am not able to get this working. I think I have to use a while loop and check all already existing integers in the vector against the new random to be added number and if it's already in there generate a new random number and check again, etc. but I don't know

I am a beginner and this is really hard. Can someone maybe give me a hint? I would appreciate it... thank you so much

Answer 1

You can populate your vector with values 0..N-1 (or your pool values), and thereafter shuffle it. See example:

// Initialize
for(i = 0; i < N; i++)
  arr[i] = i;

// shuffle
for(i = N - 1; i > 0; i--) {
  j = rand() % i;
  swap(arr[i], arr[j]);
}

Answer 2

I think your best bet is to create a vector to store the unrandomized integers, then another vector to store a randomized subset.

randomly chooose a number from your unrandomized integer vector, add that number to the randomized subset vector, then remove it from your unrandomized integer vector.

Now your unrandomized integer vector is one smaller, so randomly choose a number on the new smaller vector, add it to the randomized subset vector, and remove it from the unrandomized vector. Repeat.

Here's what it might look like

---

Unrandomized

{0, 1, 2, 3, 4, 5, 6, 7}

Randomized

{}

Choose random index: 5

Yields =>

---

Unrandomized

{0, 1, 2, 3, 5, 6, 7} //Removed 4 because it was at index #5

Randomized

{5}

Choose Random Index: 0

Yields =>

---

Unrandomized

{1, 2, 3, 5, 6, 7}

Randomized

{5, 0}

Choose Random Index: 6

Yields=>

---

Unrandommized

{1, 2, 3, 5, 6} // 7 removed at index #6

Randomized

{5, 0, 7}

---

And say you only have to pick do 3 random values here so you end up with 5, 0, 7. This method ensures no duplicates. I think there is an easier way using an inline function but I don't know it and the above should suffice.