/*
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(int $N, int $M): array {
if ($M <= 0 || $N < $M) {
throw new InvalidArgumentException("Invalid N or M: require N >= M >= 1");
}
$cuts = [];
$used = []; // ensures uniqueness
// Generate UNIQUE cut points
while (count($cuts) < $M - 1) {
$c = rand(1, $N - 1);
if (!in_array($c, $used, true)) {
$used[] = $c;
$cuts[] = $c;
}
}
// Sort the cut points
sort($cuts);
// Build the parts
$parts = [];
$prev = 0;
foreach ($cuts as $c) {
$parts[] = $c - $prev; // guaranteed >= 1
$prev = $c;
}
$parts[] = $N - $prev; // last part, also >= 1
return $parts;
}
$N = 30;
$M = 5;
$parts = split_into_random_parts($N, $M);
echo "Splitting N = $N into M = $M random parts:\n";
foreach ($parts as $p) {
echo $p . " ";
}
/*
run:
Splitting N = 30 into M = 5 random parts:
3 6 13 7 1
*/