How to split a number N into M random positive parts whose sum is exactly N in PHP

1 Answer

0 votes
/*
    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 

*/

 



answered Jul 19 by avibootz

Related questions

...