/*
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
function split_into_random_parts(N, M) {
if (M <= 0 || N < M) {
throw new Error("Invalid N or M: require N >= M >= 1");
}
const cuts = [];
const used = new Set(); // ensures uniqueness
// Generate UNIQUE cut points
while (cuts.length < M - 1) {
const c = 1 + Math.floor(Math.random() * (N - 1));
if (!used.has(c)) {
used.add(c);
cuts.push(c);
}
}
// Sort the cut points
cuts.sort((a, b) => a - b);
// Build the parts
const parts = [];
let prev = 0;
for (const c of cuts) {
parts.push(c - prev); // guaranteed >= 1
prev = c;
}
parts.push(N - prev); // last part, also >= 1
return parts;
}
// Usage
const N = 30;
const M = 5;
const parts = split_into_random_parts(N, M);
console.log(`Splitting N = ${N} into M = ${M} random parts:`);
console.log(parts.join(" "));
/*
run:
Splitting N = 30 into M = 5 random parts:
1 23 1 2 3
*/
