use rand::rng;
/*
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.
*/
/*
Paper Run (Dry Run) of the Random-Sum Program
---------------------------------------------
Input:
n = 50
k = 7
We need (k - 1) = 6 random cut points in the range [1, 49].
Simulated rand() outputs (rand() % 49):
12, 3, 40, 25, 7, 33
After adding +1 (because the code uses 1 + rand() % (n - 1)):
cuts = {13, 4, 41, 26, 8, 34}
Step 1: Sort the cut points
cuts → {4, 8, 13, 26, 34, 41}
Step 2: Convert cut points into segment lengths
prev = 0
out[0] = 4 - 0 = 4
prev = 4
out[1] = 8 - 4 = 4
prev = 8
out[2] = 13 - 8 = 5
prev = 13
out[3] = 26 - 13 = 13
prev = 26
out[4] = 34 - 26 = 8
prev = 34
out[5] = 41 - 34 = 7
prev = 41
out[6] = 50 - 41 = 9 (final segment)
Final result:
parts = {4, 4, 5, 13, 8, 7, 9}
Verification:
4 + 4 + 5 + 13 + 8 + 7 + 9 = 50
Output:
Random parts that sum to 50:
4 4 5 13 8 7 9
Sum = 50
*/
fn generate_random_sum(n: i32, k: i32) -> Vec<i32> {
if k <= 0 || n < k {
// k positive integers must sum to n → minimum sum is k
panic!("Invalid n or k");
}
let mut rng = rng(); // thread-local RNG (rand 0.9+)
// To ensure positive integers, we need (k - 1) DISTINCT cut points
// in the range [1, n - 1]. We sample indices from 0..(n-1) without replacement.
let sample = rand::seq::index::sample(&mut rng, (n - 1) as usize, (k - 1) as usize);
// Convert to 1-based indices and collect into a vector
let mut cuts: Vec<i32> = sample.into_iter().map(|idx| (idx + 1) as i32).collect();
// Sort the cut points so we can compute segment lengths
cuts.sort_unstable();
let mut result: Vec<i32> = Vec::with_capacity(k as usize);
let mut prev: i32 = 0;
// Convert cut points into segment lengths
for c in cuts {
result.push(c - prev);
prev = c;
}
// Last segment: from last cut to n
result.push(n - prev);
result
}
fn main() {
let n: i32 = 50; // total sum
let k: i32 = 7; // number of random parts
let parts = generate_random_sum(n, k);
println!("Random parts that sum to {}:", n);
for x in &parts {
print!("{} ", x);
}
println!();
// Verify sum
let sum: i32 = parts.iter().sum();
println!("Sum = {}", sum);
}
/*
run:
Random parts that sum to 50:
5 5 13 7 5 9 6
Sum = 50
*/
