import 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
def split_into_random_parts(N, M):
if M <= 0 or N < M:
raise ValueError("Invalid N or M: require N >= M >= 1")
cuts = []
used = set() # ensures uniqueness
# Generate UNIQUE cut points
while len(cuts) < M - 1:
c = random.randint(1, N - 1)
if c not in used:
used.add(c)
cuts.append(c)
# Sort the cut points
cuts.sort()
# Build the parts
parts = []
prev = 0
for c in cuts:
parts.append(c - prev) # guaranteed >= 1
prev = c
parts.append(N - prev) # last part, also >= 1
return parts
if __name__ == "__main__":
N = 30
M = 5
parts = split_into_random_parts(N, M)
print(f"Splitting N = {N} into M = {M} random parts:")
print(" ".join(str(p) for p in parts))
"""
run:
Splitting N = 30 into M = 5 random parts:
3 9 10 3 5
"""
