This is just a problem I thought of while I was in bed last night :) .
How do you split a number, let's call it N, in M random parts, so that each part has the same probability to be a number from 0 to N.
Eg: N= 5, M=3
The algorithm should return an array like one of these:
[0,2,3] //0 + 2 +3 =5
[1,1,3]
[0,0,5]
[3,2,0]
[2,2,1]
...etc
The programming languange doesn't really matter.
I just subscribed to share my results about this particular problem. I've come to a solution that pleases me, even if, obviously, it's not a 100% random number split. But it fits my needs, and it is very light on resources.
I give you the code for the method (it's a recursive method) with comments on specific parts (others are pretty straight-forward I think). The code has been made in AS3, but the language is easy to read :
/**
* This function splits a unique number into many numbers whose total equals to the one given as a parameter.
* The function only works for size equals to a power of 2, but I think it can be easily done for any size,
* by making as many "power of 2" calls as necessary to get a good final result.
* @param total The expected value of the sum of the resulting numbers
* @param minValue The minimum value each number can take
* @param maxValue The maximum value each number can take
* @param size The number of numbers we want to split the total into
* @param stepNum The step number of the recursive calls. Used to enhance the results of the algorithm.
* @return
*/
private function splitTotalInTwo(total:int, minValue:int, maxValue:int, size:int, stepNum:int):Vector.<int>
{
var result:Vector.<int> = new Vector.<int>();
// we determine the min and max values allowed for the random generated number so that it doesn't
// make the second group impossible to process with success
var minRand:int = Math.max(size * minValue, total - (size * maxValue));
var maxRand:int = Math.min(size * maxValue, total - (size * minValue));
// the balanceFactor is used to make the split tighter in the early stages of the recursive algorithm,
// therefore ensuring a best number distribution in the end.
// You can comment the next three lines to see the number distribution of th inital algorithm.
// You can alsocchange the balancefactor to get which results you like most.
// This var good also be passed as parameter to fine tune the algorithm a little bit more.
var balanceFactor:Number = 0.4;
var delta:int = Math.floor((maxRand - minRand) * (0.4 / stepNum));
minRand += delta;
maxRand -= delta;
var random:int = Math.floor(Math.random() * (maxRand - minRand)) + minRand;
if (size > 1)
{
result = result.concat(splitTotalInTwo(random, minValue, maxValue, size / 2, stepNum+1), splitTotalInTwo(total - random, minValue, maxValue, size / 2, stepNum+1));
}
else
{
result.push(random);
result.push(total - random);
}
return result;
}
Hope this helps...
Lets assume we have a method that generates a uniformly random distribution of numbers between [0,N]. An obvious way is to successively generate M random numbers in the range from [0,N] where we update N after each generation, since the sum of all generated numbers has to equal N. You would have to mathematically prove that this will result in a uniformly randomly distributed collection of pairs [x1,x2,....,xM]. I would say that this is not trivial. (For instance your example where the first number is randomly chosen to be 5, the following two numbers have to be zero as the sum can not exceed N=5 and therefore the randomnness is biased)
Another 'brute force' method that you might consider is generating a collection of all possible permutations [x1,x2,....,xM] where the sum x1+x2+...+xM = N. If the collection contains Y possible permutations you can then use our previously defined random generator to get a random number in the range [1,Y] and select that element from your collection
Note that this is just of the top of my head and if you want to ensure truely random uniform distributions you have to check these proposals mathematically.
Edit: I also just realized that probably, they way you described the problem, the order in which the number is split is irrelevant (i.e. [0,2,3] is the same as [2,3,0] is the same as [0,3,2]). This reduces the number of total unique permutation in the ensemble of Y groupings
You can try my approach. Initially I calculated amount of posible results and after choose random (implementation on C#):
class Program
{
private static int[,] dp;
private static void Populate(int m, int n)
{
dp[0, 0] = 1;
for (int i = 1; i <= m; i++)
{
dp[i, 0] = 1;
for (int j = 1; j <= n; j++)
{
dp[i, j] = dp[i - 1, j] + dp[i, j - 1];
}
}
}
private static int[] GetResultAt(int index, int m, int n)
{
int[] result = new int[m];
while (m > 0)
{
for (int i = 0; i <= n; i++)
{
if (index <= dp[m - 1, i] && dp[m - 1, i] > 0)
{
m--;
result[m] = n - i;
n = i;
break;
}
index = index - dp[m - 1, i];
}
}
return result;
}
static void Main(string[] args)
{
int n = 5;
int m = 3;
dp = new int[m + 1, n + 1];
Populate(m, n);
int randomPosition = 7;// Random value from 1 and dp[m,n] range.
int[] result = GetResultAt(randomPosition, m, n);
Console.WriteLine(result);
}
}
Define required m, n and randomPosition to get result.
Complexity of this algo is O(M*N) for precalc and O(M+N) for get a random array.
public static Integer[] sliceUnequally(int value, int numberOfSlices) {
if (numberOfSlices > value) {
throw new IllegalArgumentException(
String.format("!!! Cannot carve %d into %d slices", value, numberOfSlices));
}
final Integer[] slices = new Integer[numberOfSlices];
int allocated = numberOfSlices;
for (int i = 0; i < numberOfSlices; i++) {
if (i == (numberOfSlices - 1)) {
slices[i] = 1 + (value - allocated);
} else {
int slice = new Double((value - allocated) * random.nextDouble()).intValue();
slices[i] = 1 + slice;
allocated += slice;
}
}
return slices;
}
