4
\$\begingroup\$

There is a nice algorithm to randomly choose an element from a list in a single pass:

Pass through the list keeping the element chosen so far (X) and the number of elements processed (N). When processing element Y, let X:=Y with probability 1/N. When nothing is left, return X.

I implemented this using templates:

template <typename T>
const T& chooseImpl(T const& cur, int total) {
  return cur;
}

template <typename T, typename... Args>
const T& chooseImpl(T const& chosen, int total,  T const& next, Args... rest) {
  const T& nextChosen = (rand() % total == 0) ? next : chosen;
  return chooseImpl(nextChosen, total + 1, rest...);
}

template <typename T, typename... Args>
const T& choose(T const& first, Args... rest) {
  return chooseImpl(first, 2, rest...);
}

Example usage:

choose(1, 2, 3, 4, 5, 6); // returns a random number between 1 and 6.
choose(1); // always returns 1.

I only have a problem when choosing from C strings: choose("one", "two", "three");

note: template argument deduction/substitution failed:

deduced conflicting types for parameter ‘const T’ (‘char [4]’ and ‘const char*’)

\$\endgroup\$
2
\$\begingroup\$

Here's a version of your code which works with C-Strings by using std::decay to turn any array arguments into pointers.

This also uses perfect forwarding in the recursion, to preserve argument types, just in case unconditional conversion to a const reference is inappropriate.

I'm making this Community Wiki, because it's more of an answer to your question about C-Strings, rather than a code review (ok, little review: rand() is usually so poorly implemented, you should use something from <random>, like std::mt19937, otherwise, thumbs up!).

#include <iostream>
#include <type_traits>
#include <utility>
#include <string>
#include <cstdlib>

template <typename T>
using decay_t = typename std::decay<T>::type;

template <typename T>
decay_t<T> chooseImpl(T&& cur, int total) {
  return cur;
}

template <typename T, typename U, typename... Args>
decay_t<T> chooseImpl(T&& chosen, int total,  U&& next, Args&&... rest) {
  decay_t<T> nextChosen = (std::rand() % total == 0) ? next : chosen;
  return chooseImpl(nextChosen, total + 1, std::forward<Args>(rest)...);
}

template <typename T, typename... Args>
decay_t<T> choose(T&& first, Args&&... rest) {
  return chooseImpl(std::forward<T>(first), 2, std::forward<Args>(rest)...);
}

int main() {
    std::srand(time(0));
    for(int i=0; i<4; ++i) {
        auto c = choose("one", "two", "three");
        std::cout << c << ' ';
    }
    std::cout << '\n';
    for(int i=0; i<4; ++i) {
        auto c = choose(256, 512, 1024, 13);
        std::cout << c << ' ';
    }
    std::cout << '\n';
    const std::string s[7] = {"Aa", "Bb", "Cc", "Dd", "Ee", "Ff", "Gg"};
    for(int i=0; i<4; ++i) {
        auto c = choose(s[0],s[1],s[2],s[3],s[4],s[5],s[6]);
        std::cout << c << ' ';
    }
    std::cout << '\n';
}

Here is an example of the output:

two three one two 
13 1024 1024 256 
Bb Ff Ee Ee 
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.