#include <stdio.h>
#include <stdlib.h>
#include <time.h>
/*
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.
*/
/* Check if value exists in array */
int exists(int *arr, int size, int value) {
for (int i = 0; i < size; i++) {
if (arr[i] == value) return 1;
}
return 0;
}
/* Generate M random positive parts summing to N */
void split_into_random_parts(int N, int M, int *parts) {
if (M <= 0 || N < M) {
fprintf(stderr, "Error: require N >= M >= 1\n");
exit(1);
}
int *cuts = malloc((M - 1) * sizeof(int));
if (!cuts) {
fprintf(stderr, "Memory allocation failed\n");
exit(1);
}
srand((unsigned)time(NULL));
/* Generate UNIQUE cut points in [1, N-1] */
int count = 0;
while (count < M - 1) {
int c = 1 + rand() % (N - 1);
if (!exists(cuts, count, c)) {
cuts[count++] = c;
}
}
/* Sort the cut points */
for (int i = 0; i < M - 2; i++) {
for (int j = i + 1; j < M - 1; j++) {
if (cuts[j] < cuts[i]) {
int tmp = cuts[i];
cuts[i] = cuts[j];
cuts[j] = tmp;
}
}
}
/* Build strictly positive parts */
int prev = 0;
for (int i = 0; i < M - 1; i++) {
parts[i] = cuts[i] - prev;
prev = cuts[i];
}
parts[M - 1] = N - prev;
free(cuts);
}
int main(void) {
int N = 30;
int M = 5;
int parts[5];
split_into_random_parts(N, M, parts);
printf("Splitting N = %d into M = %d random positive parts:\n", N, M);
for (int i = 0; i < M; i++) {
printf("%d ", parts[i]);
}
return 0;
}
/*
run:
Splitting N = 30 into M = 5 random positive parts:
11 1 9 7 2
*/
