patterncppMinor

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

Submitted by: @import:stackexchange-codereview·Mar 10, 2026·

Viewed 0 times

templateelementswithchooseuniformrandomlydistributionfrom

Problem

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 
const T& chooseImpl(T const& cur, int total) {
  return cur;
}

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

Solution

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 `, like std::mt19937

, otherwise, thumbs up!).

#include 
#include 
#include 
#include 
#include 

template 
using decay_t = typename std::decay::type;

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

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

template 
decay_t choose(T&& first, Args&&... rest) {
  return chooseImpl(std::forward(first), 2, std::forward(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
`

Code Snippets

#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';
}

Context

StackExchange Code Review Q#131153, answer score: 2

Revisions (0)

No revisions yet.