import kotlin.random.Random
/*
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
fun splitIntoRandomParts(N: Int, M: Int): List<Int> {
if (M <= 0 || N < M) {
throw IllegalArgumentException("Invalid N or M: require N >= M >= 1")
}
val cuts = mutableListOf<Int>()
val used = mutableSetOf<Int>() // ensures uniqueness
// Random number generator
val rng = Random
// Generate UNIQUE cut points
while (cuts.size < M - 1) {
val c = rng.nextInt(1, N) // range [1, N-1]
if (c !in used) {
used.add(c)
cuts.add(c)
}
}
// Sort the cut points
cuts.sort()
// Build the parts
val parts = mutableListOf<Int>()
var prev = 0
for (c in cuts) {
parts.add(c - prev) // guaranteed >= 1
prev = c
}
parts.add(N - prev) // last part, also >= 1
return parts
}
fun main() {
val N = 30
val M = 5
val parts = splitIntoRandomParts(N, M)
println("Splitting N = $N into M = $M random parts:")
println(parts.joinToString(" "))
}
/*
run:
Splitting N = 30 into M = 5 random parts:
3 13 6 3 5
*/
