2

My goal is creating an array of 5 unique integers between 1 and 20. Is there a better algorithm than what I use below?

It works and I think it has a constant time complexity due to the loops not being dependent on variable inputs, but I want to find out if there is a more efficient, cleaner, or simpler way to write this.

int * getRandom( ) {

  static int choices[5] = {};
  srand((unsigned)time(NULL));
   
  for (int i = 0; i < 5; i++) {

    int generated = 1 + rand() % 20;
    for (int j = 0; j < 5; j++){
      if(choices[j] == generated){
        i--;
      }
    }
    
    choices[i] = generated;
    cout << choices[i] << endl;
  }

  return choices;
}

Thank you so much for any feedback. I am new to algorithms.

JaMiT
  • 14,422
  • 4
  • 15
  • 31
Rectanguloid
  • 25
  • 4
  • 1
    I'm not sure what exactly this is doing, so I suspect there's a cleaner and simpler way to write it. You have `i` as an index of the outer loop, but then the inner loop _also_ messes with `i`? Can you verbally describe how this algorithm generates 5 unique integers? See [rubber duck debugging](https://en.wikipedia.org/wiki/Rubber_duck_debugging) – Nathan Pierson Sep 03 '21 at 04:40
  • 4
    Don’t seed your random number generator in the function that uses it. – Davis Herring Sep 03 '21 at 04:45
  • 1
    Using `% 20` introduces a bias into your random numbers, so they won't be as random as they should be. – Mark Ransom Sep 03 '21 at 04:52
  • You have a strange phrasing in your title: *"Is there a better algorithm [...] in C++?"* Algorithms are abstract, not limited to a single language. The language may influence which algorithms are easy to implement, but not which algorithms exist. (Plus, there is the advice to not force a tag into the title in [Help: Tagging](https://stackoverflow.com/help/tagging).) – JaMiT Sep 03 '21 at 04:56
  • There is no requirement about how random the numbers should be, so returning (1,2,3,4,5) every time meets the spec. – n. m. could be an AI Sep 03 '21 at 05:55
  • I opted for a "cleaner" example, using what's available in C++. Mostly to show you how to use C++'s way of genrating random numbers and how to combine life-time management of objects with one time initialization of statics. – Pepijn Kramer Sep 03 '21 at 06:49
  • You can run the [Fisher-Yates algorithm](https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle) for just 5 steps instead of 20 (no, in fact 19). This algorithm gives a random permutation of N objects and is often used to implement the C++ [std::shuffle function](https://en.cppreference.com/w/cpp/algorithm/random_shuffle). The Wikipedia article is well written. – jpmarinier Sep 03 '21 at 08:50

3 Answers3

2

The simplest I can think about is just create array of all 20 numbers, with choices[i] = i+1, shuffle them with std::random_shuffle and take 5 first elements. Might be slower, but hard to introduce bugs, and given small fixed size - might be fine.

BTW, your version has a bug. You execute line choices[i] = generated; even if you find the generated - which might create a copy of generated value. Say, i = 3, generated is equal to element at j = 0, now your decrement i and assign choices[2] - which becomes equal to choices[0].

Michael Entin
  • 7,189
  • 3
  • 21
  • 26
  • Thank you. I am not concerned with speed for this project, so this should work fine. Also thank you for the bug explanation. I ran it a few more times and saw several outputs with 6 numbers and duplicates. – Rectanguloid Sep 03 '21 at 05:03
2

C++17 code with explanation of why and what. If you have any questions left don't hesitate to ask, I'm happy to help

#include <iostream>
#include <array>
#include <string>
#include <random>
#include <type_traits>

// container for random numbers.
// by putting the random numbers + generator inside a class
// we get better control over the lifecycle.
// e.g. what gets called when.
// Now we know the generation gets called at constructor time.
class integer_random_numbers
{
public:
    // use std::size_t for things used in loops and must be >= 0
    integer_random_numbers(std::size_t number, int minimum, int maximum)
    {
        // initialize the random generator to be trully random
        // look at documentation for <random>, it is the C++ way for random numbers
        std::mt19937 generator(std::random_device{}());

        // make sure all numbers have an equal chance. range is inclusive 
        std::uniform_int_distribution<int> distribution(minimum, maximum);

        // m_values is a std::vector, which is an array of which
        // the length be resized at runtime.  
        for (auto n = 0; n < number; ++n)
        {
            int new_random_value{};

            // generate unique number
            do
            {
                new_random_value = distribution(generator);
            } while (std::find(m_values.begin(), m_values.end(), new_random_value) != m_values.end());
        
            m_values.push_back(new_random_value);
        }
    }

    // give the class an array index operator
    // so we can use it as an array later
    int& operator[](const std::size_t index)
    {
        // use bounds checking from std::vector
        return m_values.at(index);
    }

    // reutnr the number of numbers we generated
    std::size_t size() const noexcept
    {
        return m_values.size();
    }

private:
    // use a vector, since we specify the size at runtime.
    std::vector<int> m_values;
};

// Create a static instance of the class, this will
// run the constructor only once (at start of program)
static integer_random_numbers my_random_numbers{ 5, 1, 20 };

int main()
{
    // And now we can use my_random_numbers as an array
    for (auto n = 0; n < my_random_numbers.size(); ++n)
    {
        std::cout << my_random_numbers[n] << std::endl;
    }
}
Pepijn Kramer
  • 9,356
  • 2
  • 8
  • 19
1
  1. Generate 5 random numbers from 1 to 16, allowing duplicates
  2. Sort them
  3. Add 1 to the 2nd number, 2 to the 3rd, 3 to 4th, and 4 to the 5th.

The last step transforms the range from [1,16] to [1,20] by remapping the possible sequences with duplicates into sequences with unique integers. [1,2,10,10,16], for example, becomes [1,3,12,13,20]. The transformation is completely bijective, so you never need to discard and resample.

Matt Timmermans
  • 53,709
  • 3
  • 46
  • 87
  • 3
    If we are trying to sample uniformly from all sets of 5 distinct integers in [1,20], then I don't think this does it; it has bias. There are 5!=120 sequences we could generate at step 1 that contain the numbers 1,2,3,4,5 in some order, but only 1 that contains 1,1,1,1,1, so by step 3 the sequence `[1,3,5,7,9]` is 120 times more likely to be generated than `[1,2,3,4,5]`. – Nate Eldredge Sep 03 '21 at 04:56
  • Yes, it's not completely uniform over all the sets of unique integers. – Matt Timmermans Sep 03 '21 at 05:12