How to produce random numbers so that their sum is equal to given number?

Question

I want to produce X random numbers, each from the interval <0; Y> (given Y as a maximum of each number), but there is restriction that the sum of these numbers must be equal to Z.

Example: 5 Randoms numbers, each max 6 and the sum must be equal to 14, e.g: 0, 2, 6, 4, 2

Is there already a C/C++ function that could do something like that?

Personally I couldn't come up with more than some ugly if-else-constucts.

Answer 1

Since you know how many numbers you need, generate them from the given distribution but without further conditions, store them, compute the actual sum, and scale them all up/down to get the desired sum.

Answer 2

LiHo's answer looks pretty similar to my second suggestion, so I'll leave that, but here's an example of the first. It could probably be improved, but it shouldn't have any tragic bugs. Here's a live sample.

#include <algorithm>
#include <array>
#include <random>

std::random_device rd;
std::mt19937 gen(rd());

constexpr int MAX = 14;
constexpr int LINES = 5;

int sum{};
int maxNum = 6;
int minNum{};

std::array<int, LINES> nums;

for (int i = 0; i < LINES; ++i) {
    maxNum = std::min(maxNum, MAX - sum);

    // e.g., after 0 0, min is 2 because only 12/14 can be filled after
    int maxAfterThis = maxNum * (LINES - i - 1);
    minNum = std::min(maxNum, std::max(minNum, MAX - sum - maxAfterThis));
    
    std::uniform_int_distribution<> dist(minNum, maxNum);
    int num = dist(gen);
    
    nums[i] = num;
    sum += num;
}

std::shuffle(std::begin(nums), std::end(nums), gen);

Creating that ditribution every time could potentially slow it down (I don't know), but the range has to go in the constructor, and I'm not one to say how well distributed these numbers are. However, the logic is pretty simple. Aside from that, it uses the nice, shiny C++11 <random> header.

We just make sure no remaining number goes over MAX (14) and that MAX is reached by the end. minNum is the odd part, and that's due to how it progresses. It starts at zero and works its way up as needed (the second part to std::max is figuring out what would be needed if we got 6s for the rest), but we can't let it surpass maxNum. I'm open to a simpler method of calculating minNum if it exists.

Answer 3

NOTE: this solution was written when the question specified a "MAX SUM" parameter, implying a sum of less than that amount was equally acceptable. The question's now been edited based on the OP's comment that they meant the cumulative sum must actually hit that target. I'm not going to update this answer, but clearly it could trivially discard lesser totals at the last level of recursion.

This solution does a one-time population of a vector<vector<int>> with all the possible combinations of numbers solving the input criterion, then each time a new solution is wanted it picks one of those at random and shuffles the numbers into a random order (thereby picking a permutation of the combination).

It's a bit heavy weight - perhaps not suitable for the actual use that you mentioned after I'd started writing it ;-P - but it produces an even-weighted distribution, and you can easily do things like guarantee a combination won't be returned again until all other combinations have been returned (with a supporting shuffled vector of indices into the combinations).

#include <iostream>
#include <vector>
#include <algorithm>

using std::min;
using std::max;
using std::vector;

// print solutions...    
void p(const vector<vector<int>>& vvi)
{
    for (int i = 0; i < vvi.size(); ++i)
    {
        for (int j = 0; j < vvi[i].size(); ++j)
            std::cout << vvi[i][j] << ' ';
        std::cout << '\n';
    }
}

// populate results with solutions...
void f(vector<vector<int>>& results, int n, int max_each, int max_total)
{
    if (n == 0) return;
    if (results.size() == 0)
    {
        for (int i = 0; i <= min(max_each, max_total); ++i)
             results.push_back(vector<int>(2, i));
        f(results, n - 1, max_each, max_total);
        return;
    }

    vector<vector<int>> new_results;

    for (int r = 0; r < results.size(); ++r)
    {
        int previous = *(results[r].rbegin() + 1);
        int current_total = results[r].back();
        int remaining = max_total - current_total;
        for (int i = 0; i <= min(previous,min(max_each, remaining)); ++i)
        {
            vector<int> v = results[r];
            v.back() = i;
            v.push_back(current_total + i);
            new_results.push_back(v);
        }
    }
    results = new_results;
    f(results, n - 1, max_each, max_total);
}

const vector<int>& once(vector<vector<int>>& solutions)
{
    int which = std::rand() % solutions.size();
    vector<int>& v = solutions[which];
    std::random_shuffle(v.begin(), v.end() - 1);
    return v;
}

int main()
{
    vector<vector<int>> solutions;
    f(solutions, 5, 6, 14);
    std::cout << "All solution combinations...\n";
    p(solutions);
    std::cout << "------------------\n";
    std::cout << "A few sample permutations...\n";
    for (int n = 1; n <= 100; ++n)
    {
        const vector<int>& o = once(solutions);
        for (int i = 0; i < o.size() - 1; ++i)
            std::cout << o[i] << ' ';
        std::cout << '\n';
    }
}

Answer 4

Since you don't need the generated sequence to be uniform, this could be one of the possible solutions:

#include <iostream>
#include <vector>
#include <cstdlib>

int irand(int min, int max) {
    return ((double)rand() / ((double)RAND_MAX + 1.0)) * (max - min + 1) + min;
}

int main()
{
    int COUNT = 5,    // X
        MAX_VAL = 6,  // Y
        MAX_SUM = 14; // Z

    std::vector<int> buckets(COUNT, 0);
    srand(time(0));
    int remaining = MAX_SUM;
    while (remaining > 0)
    {
        int rndBucketIdx = irand(0, COUNT-1);
        if (buckets[rndBucketIdx] == MAX_VAL)
            continue;                       // this bucket is already full
        buckets[rndBucketIdx]++;
        remaining--;
    }

    std::cout << "Printing sequence: "; 
    for (size_t i = 0; i < COUNT; ++i)
        std::cout << buckets[i] << ' ';
}

which just simply divides the total sum to bunch of buckets until it's gone :)

Example of output: Printing sequence: 4 4 1 0 5

Answer 5

#include<iostream>
#include <cstdlib> //rand ()
using namespace std;

void main()
{
    int random ,x=5;
    int max , totalMax=0 , sum=0;
    cout<<"Enter the total maximum number : ";
    cin>>totalMax;
    cout<<"Enter the maximum number: ";
    cin>>max;
    srand(0);
    for( int i=0; i<x ; i++)
    {

        random=rand()%max+1; //range from 0 to max
        sum+=random;
        if(sum>=totalMax)
        {
            sum-=random;
            i--;
        }
        else
        cout<<random<<' ';
    }
    cout<<endl<<"Reached total maximum number "<<totalMax<<endl; 


}

I wrote this simple code
I tested it using totalMax=14 and max=3 and it worked with me hope it's what you asked for