Divide a number into random parts

First you need to decide what you mean by "random parts". For example, does this mean that over the long term you would select each partition of M into N parts the same number of times? Does the order of the parts matter? Can the parts be zero? I am sure there are other questions that could be asked.

DrClapa at 2007-7-13 14:40:51 >

Given that all numbers come from the same distribution

following solution works. The idea behind it is similar

to what dubwai suggested, but it does not create the

list. This might be important because the list of

possible combinations can be large.

public static int[] getRandomSumList(int sum, int length, int maxValue) {

int [] list = new int[length];

boolean doneFirstPass = false;

int tempSum = 0;

int i = 0;

while (!doneFirstPass || tempSum!=sum) {

tempSum = tempSum - list[i];

// OBS, any distribution can be used

list[i] = (int)(Math.random()*(maxValue+1));

tempSum = tempSum + list[i];

i++;

if (i==length) {

i = 0;

doneFirstPass = true;

}

}

return list;

}

Be aware that given the wrong parameters this solution

can take a long time to find a list.

parza at 2007-7-13 14:40:51 >

> This seems misleading, as the termination condition is based

> on randomness. Although, it is possible to predict an average

> termination time.

Maybe not misleading, but far from conclusive. In your examples,

I agree that it is surprisingly fast. However, running

getRandomSumList(1, 100, 1); demand on average

2^100 = 1.2*10^30 number of loops.

> Obviously maxValue has to be greater than sum / length, otherwise

> it would be impossible to generate any combination values that

> add up to sum.

Yes, looping forever takes a very long time. :)

> You limit the size of the maximum generated value,

> although I'm not sure why.

The 'maxValue' parameter is just part of defining the

distribution. The most general way would be to define

an interface

public interface DiscreteDistribution {

public int getInstance();

}

and then use this in the function

public static int[] getRandomSumList(int sum, int length, DiscreteDistribution dist) {

...

list[i] = dist.getInstance();

...

}

> Assuming the minValue is 1, not 0, then the total number of

> permutations of 4 numbers that add up to 1000 is:

> 165,668,499

How did you compute this?

parza at 2007-7-13 14:40:51 >

> Maybe not misleading, but far from conclusive. In your examples,

> I agree that it is surprisingly fast. However, running

> getRandomSumList(1, 100, 1); demand on average

> 2^100 = 1.2*10^30 number of loops.

There are 100 ways to create a sum of 1:

[1, 0, 0, .... ]

[0, 1, 0, .... ]

[0, 0, 1, .... ]

However, there are 2^100 combinations.

Thus, the probability is 100 / 2^100. The average number

of loops would be: 12676506002282294014967032053.76

or 1.26765*10^28

> How did you compute this?

In the link I posted earlier. I modified the code

to count the number of times the display method is called.

For the examples I gave, it took much longer to count than to

use the random search.

However, in the example you gave, the output size is only

100. Thus, counting would be extremely fast since the algorithm

runs in O(n) where n is the size of the output.

The random approach works well when the number of ways to

create the sum is large. The counting approach would work well

when the number of ways to create the sum is small.

I don't know if there's a mathematically fast way to determine the

output size or if it's possible generate a permutation based on an

index value. I'll try to figure it out if I get a chance.

rkippena at 2007-7-13 14:40:51 >

> I don't know if there's a mathematically fast way to determine

> the output size

Actually, it's quite easy. If sum = x and numParts = y then

the number of permutations is: nCr(x - 1, y - 1)

(This applies when the minimum value of each part is 1, not 0).

So in my first example, x = 1000, y = 3, then

nCr(999, 3) = 999! / (3! * (999 - 3)!) = 165,668,499

> the approach I gave above works

I'm still looking at it...

rkippena at 2007-7-13 14:40:51 >

> but not completely even. Do you know why this is or

> how to fix it?

I think being completely even requires an infinite amount

of computation.

> If I replace the splitters line with

I thought it was ok without the replacement. I'm using this

to test it and it's coming out pretty even:

public static void main(String[] args) {

int[] sum = new int[4];

int[] min = new int[4];

int[] max = new int[4];

int n = 10000000;

for (int i = 0; i < 4; i++)

min[i] = Integer.MAX_VALUE;

int goalSum = 100;

for (int i = 0; i < n; i++) {

int[] list = getRandomSumList(goalSum, sum.length);

for (int j = 0; j < list.length; j++) {

sum[j] += list[j];

if (list[j] < min[j]) min[j] = list[j];

if (list[j] > max[j]) max[j] = list[j];

}

}

System.out.println("The ideal average value is: " + (1.0 * goalSum / sum.length));

System.out.println("averages:");

for (int i = 0; i < sum.length; i++)

System.out.print((1.0 * sum[i] / n) + " ");

System.out.println("\n");

System.out.println("mins:");

for (int i = 0; i < min.length; i++)

System.out.print(min[i] + " ");

System.out.println("\n");

System.out.println("maxes:");

for (int i = 0; i < max.length; i++)

System.out.print(max[i] + " ");

System.out.println();

}

rkippena at 2007-7-20 12:20:12 >

> a + (b - a) + (c - b) + (max - c) = max

Cool, did not think of this possibility.

I think I have isolated the cause of the problem. Take

a look at this example. The sum should be 1, divided up

into 3 buckets. Then we can create following table

splitters = sorted splitters = value in buckets

0,0 = 0,0 = 0,0,1

0,1 = 0,1 = 0,1,0

1,0 = 0,1 = 0,1,0

1,1 = 1,1 = 1,0,0

Mean values in buckets = 1/4,1/2,1/4.

This can be verified by running the program. Now, if we

let the sum be 1 and we increase the number of buckets,

then the sorted splits will push the 0->1 jump around

the center of the sort. For 10 buckets the most common

sorted split will be 0,0,0,0,0,1,1,1,1,1 and

0,0,0,0,0,0,0,0,0,1 is extremely rare. This effect is

almost gone when the sum is about 100 times the number

of buckets. Conclusion: This method only works when

the number of buckets is a lot less then the sum.

I think I have found a solution that is quite fast for

any number of buckets and any sum. The idea is really

simple!!

public static int[] getRandomSumList(int sum, int length, double evenFactor) {

int [] list = new int [length];

while (sum>0) {

int sumPart = 1 + (int)(Math.random()*sum*evenFactor);

int i = (int)(Math.random()*length);

list[i] = list[i] + sumPart;

sum = sum - sumPart;

}

return list;

}

The evenFactor should be between 0 and 1 and determines

how even the numbers should be.

parza at 2007-7-20 12:20:12 >

> it looks like a binomial distribution occurs,

Yes, I was thinking the same, but I could not get

the values consistent with its density function

f(x) = nCr(n,x)*p^x*(1-p)^(n-x).

The more I dig into this problem, the more complicated

it becomes. Since the sum must be be a constant, at

least one stochastic variable must be dependent on at

least one other. Further more, if we want the same mean,

variance, or even the same distribution, every variable

in the sum must be dependent on every other. With this

in mind, let us take a look at my first solution. In

this solution the sum can be built from any distribution

and even if the variables are independent going into

the sum, the variable can not be independent when a

result is found. They become dependent because the

method is discarding many sums, but how is the

distribution effected?

Even if there has been three different solutions

presented in this thread, no one is complete. I would

like to see a solution where I can determine the

distribution of the parts and it should always be fast.

parza at 2007-7-20 12:20:12 >

The OP never defined what was meant by choosing an integer partition at random. It has been suggested by dubwai that the appropriate measure was to choose uniformly from the finite set of possible partitions. However it was also not specified as to which of the two perfectly logical sets of partitions we might be talking about.

For example if I am splitting 6 into 3 parts, it is easy to see that one of the partitions is {2,2,2} but do I count {1,1,4} {1,4,1} and {4,1,1} as three distinct partitions or do I cannonicalize it to sorted form {4,1,1} and count it as a single partition?

One might assume from the fact that the OPs list was unsorted to start with that the unsorted definition (counting 411, 141, & 114 as 3 different partitions) would be the prefered distribution, but the later comment about shuffling a result to get a final answer makes it unclear which is the prefered distribution. (Actually it makes it perfectly clear that the term "random" was being used in the the colloquial manner where it means some random unknown thing because the concept of an underlying distribution was never considered.)

It is fairly easy to see that none of the yet proposed algorithms actually returns a uniformly distributed choice among either of these two reasonable definitions of the set of distinct partitions.

It is not particularly difficult to come up with an algorithm that selects uniformly among the unordered partitions. To break the number N into K parts, just choose K-1 distinct numbers from 1 to N-1, Think of them as split points of the interval from 1 to N and then read off the lengths of the intervals. The K-1 splits points yield K intervals whose lengths will all at least 1 as long as all the splits are distinct. The discussion about how to efficiently choose K distinct elements from a set of N was a lively topic here a month or so ago.

It should be clear that every distinct choice of split points leads to a single distinct unsorted partition, and thus this algorithm will efficiently generate a uniform choice among the unsorted partitions.

It also leads to a rather simple (though very inefficient) algorithm for selecting uniformly among the sorted partitions as well. Simply run the algorithm and if the result happened to be sorted return it, otherwise run it again. This means that you will be coosing only from among the set of cannonical forms which is the other interesting distribution.

Unfortunately, given that there are K! arrangements of K terms and in general only one of them is in sorted order that means that this algorithm has a runtime that is exponential in K. Works fine for samll K.

The method that has been proposed so far, filling each slot with a random number until you happen to get the correct sum, has little hope of ever solving the harder problem of uniformly generating one of these sorted partitions. It clearly does the wrong thing if the internal distribution function is highly skewed, for example if the internal distribution chooses 1 nearly all the time and only rarely chooses some other number - it will tend to choose final partitions that are nearly all 1's with an occasional larger number. Once you know that the final result is sensitive to the internal distribution used to select candidates, you know that only one single distribution function among the infinitude available could possibly be right.

Furthermore there is no indication that there even is a correct internal distribution that would work. It seems much more likely, that once you have choosen a single number for a single slot, the distribution required to fill yet another slot is different from the first.

marlin314a at 2007-7-20 12:20:12 >