import scala.util.Random
import scala.collection.mutable
/*
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
def splitIntoRandomParts(N: Int, M: Int): Vector[Int] = {
if (M <= 0 || N < M)
throw new IllegalArgumentException("Invalid N or M: require N >= M >= 1")
val cuts = mutable.ArrayBuffer[Int]()
val used = mutable.Set[Int]() // ensures uniqueness
val rng = new Random()
// Generate UNIQUE cut points
while (cuts.size < M - 1) {
val c = 1 + rng.nextInt(N - 1)
if (!used.contains(c)) {
used += c
cuts += c
}
}
// Sort the cut points
val sortedCuts = cuts.sorted
// Build the parts
val parts = mutable.ArrayBuffer[Int]()
var prev = 0
for (c <- sortedCuts) {
parts += (c - prev) // guaranteed >= 1
prev = c
}
parts += (N - prev) // last part, also >= 1
parts.toVector
}
@main def main(): Unit = {
val N = 30
val M = 5
val parts = splitIntoRandomParts(N, M)
println(s"Splitting N = $N into M = $M random parts:")
println(parts.mkString(" "))
}
/*
run:
Splitting N = 30 into M = 5 random parts:
10 5 4 8 3
*/
