Imports System
Imports System.Collections.Generic
Imports System.Linq
Module RandomSumVB
'
' Generate k random positive integers that sum to n.
'
' Algorithm (stick-breaking / random composition):
' ------------------------------------------------
' 1. We choose (k - 1) random "cut points" in the range [1, n - 1].
' These represent where we "break" the integer n into k parts.
'
' 2. Sort the cut points.
'
' 3. Compute the differences between consecutive points
' (including 0 and n as boundaries). These differences
' are the k positive integers that sum to n.
'
' This produces a uniformly random composition of n.
'
'
' Paper Run (Dry Run) of the Random-Sum Program
' ---------------------------------------------
'
' Input:
' n = 50
' k = 7
'
' We need (k - 1) = 6 random cut points in the range [1, 49].
'
' Simulated Random() outputs (Random(49)):
' 12, 3, 40, 25, 7, 33
'
' After adding +1 (because the code uses 1 + Random(n - 1)):
' cuts = {13, 4, 41, 26, 8, 34}
'
' Step 1: Sort the cut points
' cuts → {4, 8, 13, 26, 34, 41}
'
' Step 2: Convert cut points into segment lengths
' prev = 0
'
' out[0] = 4 - 0 = 4
' prev = 4
'
' out[1] = 8 - 4 = 4
' prev = 8
'
' out[2] = 13 - 8 = 5
' prev = 13
'
' out[3] = 26 - 13 = 13
' prev = 26
'
' out[4] = 34 - 26 = 8
' prev = 34
'
' out[5] = 41 - 34 = 7
' prev = 41
'
' out[6] = 50 - 41 = 9 (final segment)
'
' Final result:
' parts = {4, 4, 5, 13, 8, 7, 9}
'
' Verification:
' 4 + 4 + 5 + 13 + 8 + 7 + 9 = 50
'
' Output:
'
' Random parts that sum to 50:
' 4 4 5 13 8 7 9
' Sum = 50
'
Function GenerateRandomSum(n As Integer, k As Integer) As List(Of Integer)
If k <= 0 OrElse n < k Then
' k positive integers must sum to n → minimum sum is k
Throw New ArgumentException("Invalid n or k")
End If
Dim rng As New Random()
Dim cuts As New List(Of Integer)(k - 1)
' Generate (k - 1) random cut points in [1, n - 1]
For i As Integer = 1 To k - 1
cuts.Add(1 + rng.Next(n - 1))
Next
' Sort the cut points so we can compute segment lengths
cuts.Sort()
Dim result As New List(Of Integer)(k)
Dim prev As Integer = 0
' Convert cut points into segment lengths
For Each c In cuts
result.Add(c - prev)
prev = c
Next
' Last segment: from last cut to n
result.Add(n - prev)
Return result
End Function
Sub Main()
Dim n As Integer = 50 ' total sum
Dim k As Integer = 7 ' number of random parts
Dim parts As List(Of Integer) = GenerateRandomSum(n, k)
Console.WriteLine("Random parts that sum to " & n & ":")
For Each x In parts
Console.Write(x & " ")
Next
Console.WriteLine()
' Verify sum
Dim sum As Integer = parts.Sum()
Console.WriteLine("Sum = " & sum)
End Sub
End Module
' run:
'
' Random parts that sum to 50:
' 8 16 1 7 12 1 5
' Sum = 50
'
