use std::collections::HashSet;
/*
Split a number n into m random positive parts that sum to n.
*/
/*
Split a number N into M random positive parts that sum to N.
Algorithm (uniform integer composition):
----------------------------------------
1. We want M positive integers p1, p2, ..., pM such that:
p1 + p2 + ... + pM = N
2. Generate (M - 1) random "cut points" in the range [1, N - 1].
Example: N = 20, M = 4 → generate 3 cuts, e.g. {3, 11, 17}
3. Sort the cut points.
4. The parts are the differences between consecutive cuts:
p1 = cut[0]
p2 = cut[1] - cut[0]
...
pM = N - cut[M-2]
This produces a uniformly random composition of N into M parts.
*/
/*
Important:
-----------
Random cut points must be UNIQUE.
If two cut points are equal, their difference becomes 0,
which produces an invalid part.
*/
// Generate m random positive parts summing to n
fn split_into_random_parts(n: i32, m: i32) -> Vec<i32> {
if m <= 0 || n < m {
panic!("Invalid n or m: require n >= m >= 1");
}
let mut cuts: Vec<i32> = Vec::with_capacity((m - 1) as usize);
let mut used: HashSet<i32> = HashSet::new(); // ensures uniqueness
// Generate UNIQUE cut points using the top-level function directly
while cuts.len() < (m - 1) as usize {
let c: i32 = rand::random_range(1..n);
if !used.contains(&c) {
used.insert(c);
cuts.push(c);
}
}
// Sort the cut points
cuts.sort();
// Build the parts
let mut parts: Vec<i32> = Vec::with_capacity(m as usize);
let mut prev: i32 = 0;
for c in cuts {
parts.push(c - prev); // guaranteed >= 1
prev = c;
}
parts.push(n - prev); // last part, also >= 1
parts
}
fn main() {
let n: i32 = 30;
let m: i32 = 5;
let parts: Vec<i32> = split_into_random_parts(n, m);
println!("Splitting n = {} into m = {} random parts:", n, m);
for p in parts {
print!("{} ", p);
}
println!();
}
/*
run:
Splitting n = 30 into m = 5 random parts:
5 3 5 6 11
*/
