import Foundation
/*
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
func splitIntoRandomParts(_ N: Int, _ M: Int) -> [Int] {
if M <= 0 || N < M {
fatalError("Invalid N or M: require N >= M >= 1")
}
var cuts: [Int] = []
var used: Set<Int> = [] // ensures uniqueness
// Generate UNIQUE cut points
while cuts.count < M - 1 {
let c = Int.random(in: 1..<N)
if !used.contains(c) {
used.insert(c)
cuts.append(c)
}
}
// Sort the cut points
cuts.sort()
// Build the parts
var parts: [Int] = []
var prev = 0
for c in cuts {
parts.append(c - prev) // guaranteed >= 1
prev = c
}
parts.append(N - prev) // last part, also >= 1
return parts
}
let N = 30
let M = 5
let parts = splitIntoRandomParts(N, M)
print("Splitting N = \(N) into M = \(M) random parts:")
print(parts.map { "\($0)" }.joined(separator: " "))
/*
run:
Splitting N = 30 into M = 5 random parts:
3 10 5 2 10
*/
