Imports System
Imports System.Collections.Generic
Module SplitRandomParts
'
' 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
Function SplitIntoRandomParts(N As Integer, M As Integer) As List(Of Integer)
If M <= 0 OrElse N < M Then
Throw New ArgumentException("Invalid N or M: require N >= M >= 1")
End If
Dim cuts As New List(Of Integer)(M - 1)
Dim used As New HashSet(Of Integer)() ' ensures uniqueness
Dim rand As New Random()
' Generate UNIQUE cut points
While cuts.Count < (M - 1)
Dim c As Integer = 1 + rand.Next(N - 1)
If Not used.Contains(c) Then
used.Add(c)
cuts.Add(c)
End If
End While
' Sort the cut points
cuts.Sort()
' Build the parts
Dim parts As New List(Of Integer)(M)
Dim prev As Integer = 0
For Each c As Integer In cuts
parts.Add(c - prev) ' guaranteed >= 1
prev = c
Next
parts.Add(N - prev) ' last part, also >= 1
Return parts
End Function
Sub Main()
Dim N As Integer = 30
Dim M As Integer = 5
Dim parts As List(Of Integer) = SplitIntoRandomParts(N, M)
Console.WriteLine("Splitting N = " & N & " into M = " & M & " random parts:")
For Each p As Integer In parts
Console.Write(p & " ")
Next
Console.WriteLine()
End Sub
End Module
' run:
'
' Splitting N = 30 into M = 5 random parts:
' 15 1 3 4 7
'
