import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.Random;
/**
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.
*/
public class SplitRandomParts {
// Generate M random positive parts summing to N
public static ArrayList<Integer> splitIntoRandomParts(int N, int M) {
if (M <= 0 || N < M) {
throw new IllegalArgumentException("Invalid N or M: require N >= M >= 1");
}
ArrayList<Integer> cuts = new ArrayList<>(M - 1);
HashSet<Integer> used = new HashSet<>(); // ensures uniqueness
Random rand = new Random();
// Generate UNIQUE cut points
while (cuts.size() < M - 1) {
int c = 1 + rand.nextInt(N - 1);
if (!used.contains(c)) {
used.add(c);
cuts.add(c);
}
}
// Sort the cut points
Collections.sort(cuts);
// Build the parts
ArrayList<Integer> parts = new ArrayList<>(M);
int prev = 0;
for (int c : cuts) {
parts.add(c - prev); // guaranteed >= 1
prev = c;
}
parts.add(N - prev); // last part, also >= 1
return parts;
}
public static void main(String[] args) {
int N = 30;
int M = 5;
ArrayList<Integer> parts = splitIntoRandomParts(N, M);
System.out.println("Splitting N = " + N + " into M = " + M + " random parts:");
for (int p : parts) {
System.out.print(p + " ");
}
System.out.println();
}
}
/*
run:
Splitting N = 30 into M = 5 random parts:
10 7 2 9 2
*/
