require 'set'
=begin
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.
=end
=begin
Important:
-----------
Random cut points must be UNIQUE.
If two cut points are equal, their difference becomes 0,
which produces an invalid part.
=end
# Generate M random positive parts summing to N
def split_into_random_parts(n, m)
if m <= 0 || n < m
raise ArgumentError, "Invalid N or M: require N >= M >= 1"
end
cuts = []
used = Set.new # ensures uniqueness
# Generate UNIQUE cut points
while cuts.length < m - 1
c = rand(1...n)
unless used.include?(c)
used.add(c)
cuts << c
end
end
# Sort the cut points
cuts.sort!
# Build the parts
parts = []
prev = 0
cuts.each do |c|
parts << (c - prev) # guaranteed >= 1
prev = c
end
parts << (n - prev) # last part, also >= 1
parts
end
# Usage
n = 30
m = 5
parts = split_into_random_parts(n, m)
puts "Splitting N = #{n} into M = #{m} random parts:"
puts parts.join(" ")
=begin
run:
Splitting N = 30 into M = 5 random parts:
2 10 6 5 7
=end
