How to generate a random bag of positive integers that sum up to an input number?

Question

A number N and a range a to b will be input by the user, with a < b < N.

The program purpose is to generate random sets of positive integers that sum up to N, with each positive integers within the range a and b.

For example,

N = 26
a = 1
b = 10

And here are some possible output of the program:

1,1,10,1,1,1,1,10
3,2,1,10,5,5
10,10,6
1,2,3,4,5,6,5

One way to do that is:

1. Generate 2 y[0],y[1] within the range

2. If the y[0]+y[1] > N, start over again.

3. If the y[0]+y[1]-N < a, start over again

4. If the y[0]+y[1]-N < b, return the set y[0], y[1], N-y[0]-y[1]

5. Else, generate y[i] within the range

6. If the y[0]+y[1]+...+y[i]-N < b, return the set y[0], y[1], ..., N-y[0]-y[1]-...-y[i]

7. Else, repeat 5-6

The problem is that the random function is slow. Is there a more efficient way to do this with less number of random?

Answer 1

I think a problem you have is that it is quite easy for there to be no valid solutions, if a is close to b

There is no valid results if N < a, and there is only one valid result for N = a. Similarly, there are no valid results if N < 2 * a and N > b

If you require that b > 2 * a then your method is guaranteed to find a valid result, and it can be simplified thus:

def greedy(N, a, b):
    while N > 0:
        next = randint(a, b)
        N -= next
        if N < a:
            next += N
            N = 0
        yield next

Answer 2

I'm focusing on the OP's real question, which is speed-- in particular, the number of times the randomization function is called, and how fast (or slow) it is. I don't see any issue with functional correctness.

The original algorithm only generates one random number per element, and I don't see any way to generate fewer than that. But I do have a couple suggestions.

1. Ensure you are not reseeding the random number generator every time. You only need to seed it once.

2. How does your random function generate values within the range ? If it does it iteratively (trying value after value until it finds one in range) then that could be the problem. Instead of trial and error, use the randomization function to generate a number within its own native range, then scale that range to the target domain. E.g. if it generates numbers between 0 and 2^16, divide the result by 2^16 and multiply by (b-a), then add a, then round off to the nearest whole number.

3. If the problem is scalability-- i.e. you need a very large number of result sets per a single value N-- then approach the problem backwards: generate (nonrandomly) all possible sets of integers that meet the criteria, store them in an array of sets, then use a randomization function to choose an index into the array. There are various ways to compute the full list, the simplest being a set of m-1 nested loops where m = the maximum number of elements in a set (the last element is computed as the difference between the accumulator and N). Noteworthy of this approach is that it will offer performance that is completely predictable. However this is a poor solution if you only need a small number of sets, or if you expect m to be very large.

Answer 3

Check the below solution, minimal usage of random to find the sequence of numbers between a & b which would sum up to N;

1. sum = 0; previous = 0; previousIdx=0; begin = 0;  (0:index of a; s:index of b)
2. selectArray (array of numbers which sums to N)
3. loop i : begin through s
4.  if sum+number(i)<=N
5.    previous = number(i)
6.    previousIdx = i
7.    sum = sum + number(i)
8.    add number(i) in selectArray
9. if sum < N
10.   sum = sum - previous 
11.  remove last from selectArray
12.  begin = random number between 0 & s
13.  go to step 3 
14. if sum =  N
15.   return selectArray  

Wrap this algorithm in an outside loop to continue several times to give multiple combinations forming the sum to N, changing the begin index everytime.

Answer 4

I think this will be random without starting over

while (true)
{
    next = rand.Next(a, b);  // inclusive
    if(sum + next == c)
    {
        list.Add(next);
        return list;
    }
    if(sum + next + a == c)
    {
        list.Add(next);
        list.Add(a);
        return list;
    }
    if(sum + next + a > c)
    {
        list.Add(c - sum);
        return list;
    }
    list.Add(next);
}