Dividing a number into m parts uniformly randomly

Question

How do I divide a large positive integer n into m parts uniformly randomly. Post-condition: Adding up all the m parts should give n.

Below is my attempt(in java like pseudocode), but I don't think it will give me uniformly random distribution. I am first finding the average part avg by dividing n/m. Then I am generating m-1 random numbers which are around avg in magnitude(by alternately generating random numbers between 0 & avg, and *avg & 2*avg*. Then I am subtracting the sum of these m-1 numbers from original number n and setting that as the m'th part.

Assume that the function rand(x, y) returns a random number uniformly between x and y.

int[] divideUniformlyRandomly(int n, int m)
{
    int[] res = new int[m];
    int avg = n / m;
    int sum = 0;
    bool alternator = false;
    for(int i = 0; i < m - 1; i++)
    {
        if(alternator == false)
        {
            res[i] = rand(0, avg);
            alternator = true;
        }
        else
        {
            res[i] = rand(avg, 2*avg);
            alternator = false;
        }
        sum += res[i];
    }
    res[m-1] = n - sum;
    return res;
}

Do you want the actual code to be in java? Please put a language tag, otherwise nobody will see your question later, since `random` is not a very popular tag. — Tudor, Mar 27 '12 at 14:26
possible duplicate of [Getting N random numbers that the sum is M](http://stackoverflow.com/questions/2640053/getting-n-random-numbers-that-the-sum-is-m). Also related: http://stackoverflow.com/questions/5622608/choosing-n-numbers-with-fixed-sum — finnw, Mar 27 '12 at 15:26
Also check out [this question](http://stackoverflow.com/questions/8064629/random-numbers-that-add-to-100-matlab) which has a very good answer. — finnw, Mar 27 '12 at 15:36
Whoa! I need to work on my searching skills. I tried finding possible duplicates but couldn't. — Prabhakar, Mar 27 '12 at 15:43

score 4 · Accepted Answer · answered Jun 30 '12 at 07:13

public double[] divideUniformlyRandomly(double number, int part) {
    double uniformRandoms[] = new double[part];
    Random random = new Random();

    double mean = number / part;
    double sum = 0.0;

    for (int i=0; i<part / 2; i++) {
        uniformRandoms[i] = random.nextDouble() * mean;

        uniformRandoms[part - i - 1] = mean + random.nextDouble() * mean;

        sum += uniformRandoms[i] + uniformRandoms[part - i -1];
    }
    uniformRandoms[(int)Math.ceil(part/2)] = uniformRandoms[(int)Math.ceil(part/2)] + number - sum;

    return uniformRandoms;
}

score 0 · Answer 2 · answered Mar 29 '12 at 12:41

0

You should divide n in m parts using m - 1 uniformy distributed fences. Your code could be :

int[] divideUniformlyRandomly(int n, int m)
{
    int[] fences = new int[m-1];
    for(int i = 0; i < m - 2; i++)
    {
        fences[i] = rand(0, n-1);
    }
    Arrays.sort(fences);

    int[] result = new int[m];
    result[0] = fences[0];
    for(int i = 1; i < m - 2; i++)
    {
        result[i] = fences[i+1] - fences[i];
    }
    result[m-1] = n - 1 - fences[m-2];

    return result;
}

To illustrate this : enter image description here

answered Mar 29 '12 at 12:41

olivieradam666

4,522
2
20
25

have you plotted the values you get for this? are they uniformly distributed? – andrew cooke Mar 29 '12 at 12:52
@andrewcooke I just saw that my answer is a duplicate of http://stackoverflow.com/a/8064754/436792. The most upvoted answer to the same question actually says that this method produces a uniform distribution. – olivieradam666 Mar 29 '12 at 13:02
ok, i was asking whether the individual values are uniform. which is not the same as asking whether the points are uniformly distributed on an n-1 dimensional plane. i still don't understand fully, but my original plot is irrelevant. – andrew cooke Mar 29 '12 at 14:26

Dividing a number into m parts uniformly randomly

2 Answers2

Linked