#include <stdio.h>
#include <stdlib.h>
#include <time.h>
/*
Generate k random positive integers that sum to n.
Algorithm (stick‑breaking / random composition):
------------------------------------------------
1. 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 rand() outputs (rand() % 49):
12, 3, 40, 25, 7, 33
After adding +1 (because the code uses 1 + rand() % (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
*/
/* qsort comparator for integers */
int cmp_int(const void *a, const void *b) {
return (*(int*)a - *(int*)b);
}
/* Generate k random positive integers that sum to n */
void generate_random_sum(int n, int k, int *out) {
if (k <= 0 || n < k) {
/* k positive integers must sum to n → minimum sum is k */
fprintf(stderr, "Invalid n or k\n");
exit(1);
}
int *cuts = malloc((k - 1) * sizeof(int));
if (!cuts) {
fprintf(stderr, "Memory allocation failed\n");
exit(1);
}
/* Seed RNG with current time */
srand((unsigned)time(NULL));
/* Generate (k - 1) random cut points */
for (int i = 0; i < k - 1; ++i) {
cuts[i] = 1 + rand() % (n - 1); /* uniform in [1, n-1] */
}
/* Sort the cut points */
qsort(cuts, k - 1, sizeof(int), cmp_int);
int prev = 0;
/* Convert cut points into segment lengths */
for (int i = 0; i < k - 1; ++i) {
out[i] = cuts[i] - prev;
prev = cuts[i];
}
/* Last segment: from last cut to n */
out[k - 1] = n - prev;
free(cuts);
}
int main(void) {
int n = 50; /* total sum */
int k = 7; /* number of random parts */
int *parts = malloc(k * sizeof(int));
if (!parts) {
fprintf(stderr, "Memory allocation failed\n");
return 1;
}
generate_random_sum(n, k, parts);
printf("Random parts that sum to %d:\n", n);
for (int i = 0; i < k; ++i) {
printf("%d ", parts[i]);
}
printf("\n");
/* Verify sum */
int sum = 0;
for (int i = 0; i < k; ++i) sum += parts[i];
printf("Sum = %d\n", sum);
free(parts);
return 0;
}
/*
run:
Random parts that sum to 50:
4 1 0 3 8 18 16
Sum = 50
*/
