C++ template to randomly choose from N elements with uniform distribution

Question

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*’)

Answer 1

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