#include <iostream>
#include <vector>
#include <random>
#include <algorithm>
#include <numeric>
/*
Generate k random positive integers that sum to n.
Algorithm (stick-breaking / random composition):
------------------------------------------------
1. We choose (k - 1) random "cut points" in the range [1, n - 1].
These represent where we "break" the integer n into k parts.
2. Sort the cut points.
3. Compute the differences between consecutive points
(including 0 and n as boundaries). These differences
are the k positive integers that sum to n.
This produces a uniformly random composition of n.
*/
std::vector<int> generate_random_sum(int n, int k) {
if (k <= 0 || n < k) {
// k positive integers must sum to n → minimum sum is k
throw std::invalid_argument("Invalid n or k");
}
std::random_device rd; // non-deterministic seed
std::mt19937 gen(rd()); // Mersenne Twister engine
std::uniform_int_distribution<> dist(1, n - 1);
std::vector<int> cuts;
cuts.reserve(k - 1);
// Generate (k - 1) random cut points
for (int i = 0; i < k - 1; ++i) {
cuts.push_back(dist(gen));
}
// Sort the cut points so we can compute segment lengths
std::sort(cuts.begin(), cuts.end());
std::vector<int> result;
result.reserve(k);
int prev = 0;
// Convert cut points into segment lengths
for (int c : cuts) {
result.push_back(c - prev);
prev = c;
}
// Last segment: from last cut to n
result.push_back(n - prev);
return result;
}
int main() {
int n = 50; // total sum
int k = 7; // number of random parts
auto parts = generate_random_sum(n, k);
std::cout << "Random parts that sum to " << n << ":\n";
for (int x : parts) {
std::cout << x << " ";
}
std::cout << "\n";
// Verify sum
std::cout << "Sum = "
<< std::accumulate(parts.begin(), parts.end(), 0)
<< "\n";
}
/*
run:
Random parts that sum to 50:
2 3 14 7 1 13 10
Sum = 50
*/
