Generate random number and guaranteed to cover all between the given domain?

Question

Could someone help me with generating random numbers between 0-71 while also guarantee it WILL cover all numbers from 0 to 71 inclusively?

I have tried the following, but some numbers appear more than once and some don't appear at all.

int max= 71;
int min= 0;

std::random_device engine;

//initialise to -1 to make sure numbers are generated and stored properly
int randomNum = -1;

while(max> 0){
  std::uniform_int_distribution<int> randomDistributed(min,max);
  randomNum = randomDistrubuted(engine);
  std::cout << randomNum << ", ";
  max--;
}

UPDATE: This problem was raised as I intend to generate random numbers so I could shuffle my own implementation of LinkedList data structure. I wished to achieve this by creating a new list and add elements from oldList->get(randomNumber) element to the new shuffled list. Code above should actually be sufficient to achieve this, as previously mentioned last sentence before the current sentence.

Store the numbers in an [unordered set](https://en.cppreference.com/w/cpp/container/unordered_set) until you have 73 elements in the set? — Some programmer dude, May 14 '19 at 07:37
@Botje is there another way? I'm working on a project that implements own ADTs — ferics, May 14 '19 at 07:47
@Botje Please note that [`std::random_shuffle`](https://en.cppreference.com/w/cpp/algorithm/random_shuffle) was removed from C++17, you should use `std::shuffle` instead. The OP could use one of the possible implementations in that page if, for some reason, they were not allowed to use the std algorithm. — Bob__, May 14 '19 at 07:51
As long as your custom ADTs have iterators you're good. Another alternative: pick a random number `i` in [0..limit], output `numbers[i]` (which is initially just [0..72]), swap `numbers[i]` and `numbers[limit]`, and decrease `limit`. repeat until `limit < 0`. — Botje, May 14 '19 at 07:56
@Bob__ the specification requires full implementation of shuffle a LinkedList, hence I'm struggling to achieve some random number so I could get elements from one list to another unordered. — ferics, May 14 '19 at 08:00
@ChanbothSom Same idea as what I said, except you unlink random items one by one from one list (filled with [0..72]) and prepend them to another. It will be O(n^2), but that cannot be helped. — Botje, May 14 '19 at 08:31
Is there any question here, or can we assume that the original problem is solved? — anatolyg, May 14 '19 at 14:08
@anatolyg thank you for your concern. As per updated, the question has been resolved to a level of satisfaction but does not quite exactly answering the "question" in regards to "covering all digits", but enough for I would like to achieve in the note. — ferics, May 14 '19 at 14:21

score 2 · Answer 1 · answered May 14 '19 at 08:41

If you already have written an iterator for your linked list class, you could adapt one of the possible implementations of std::shuffle to operate on a forward iterator.

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

template<class ForwardIt, class URBG>
void list_shuffle(ForwardIt first, ForwardIt last, URBG&& g)
{
    using diff_t = typename std::iterator_traits<ForwardIt>::difference_type ;
    using distr_t = std::uniform_int_distribution<diff_t>;
    using param_t = typename distr_t::param_type;
    using std::iter_swap;

    distr_t distr;
    diff_t n = std::distance(first, last);
    for (diff_t i = n - 1; i > 0; --i)
    {
        auto it = std::next(first, distr(g, param_t(0, i)));
        iter_swap(first++, it);
    }
}

int main() 
{
    std::random_device rd;
    std::mt19937 g(rd());
    std::list<int> a {1, 2, 3, 4, 5, 6, 7};


    list_shuffle(a.begin(), a.end(), g);

    for (auto const & i : a)
        std::cout << ' ' << i;
    std::cout << '\n';
}

It would be very inefficient, though, so you might prefer to copy the list into a vector, shuffle it and recreate the list from it.

I intend to generate random numbers so I could shuffle my own implementation of LinkedList data structure. I wished to achieve this by creating a new list and add elements from oldList->get(randomNumber) element to the new shuffled list. Hope this clears some doubts. — ferics, May 14 '19 at 12:30
@ChanbothSom Ok, so you have to know the size of list, n, then pick a number k between 0 and n. With `std::list` you could advance an iterator k times, push_front the value in a new list and erase that element from the source list. After that, just decrease n and repeat. How to do this with your own class depends on how you have implemented it. — Bob__, May 14 '19 at 12:48

score -1 · Answer 2 · answered May 14 '19 at 08:00

-1

This code generates 1000 random numbers. Standard function srand() generates random sequence for rand() by "seed", that it takes as a parameter. time() function takes current time, so every time sequence will be unique.

#include <random>
#include <ctime>
#include <vector>

using std::vector;

int main() {
    srand(time(0));
    vector<int> v;
    for (int i = 0, num = 0; i < 1000; ++i) {
        num = rand()%72;
        v.push_back(num);
    }
}

answered May 14 '19 at 08:00

Александр Кушниренко

210
1
12

It has the same problem as OP, though: the random number generator might generate duplicate numbers, so only part of the range is covered. – Botje May 14 '19 at 08:28
Then, why we even need random generator? If we need all the numbers from the range with only one duplicate, do we need random? – Александр Кушниренко May 14 '19 at 08:42
OP's program showed the intent to generate a random permutation of the numbers [0..72] – Botje May 14 '19 at 08:55
I intend to generate random numbers so I could shuffle my own implementation of LinkedList data structure. I wished to achieve this by creating a new list and add elements from oldList->get(randomNumber) element to the new shuffled list. Hope this clears some doubts. – ferics May 14 '19 at 12:30

Generate random number and guaranteed to cover all between the given domain?

2 Answers2