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

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?

• You didn't specify the probability distribution you want. Jan 13, 2017 at 10:53
• You say that you want to generate sets, but the sample outputs contain duplicates. Jan 13, 2017 at 10:54
• Well, I have no special probability distribution need. And if I don't mind there are duplicate numbers in the result, how should I call that? Jan 13, 2017 at 10:56
• The big problem: Define "random". Jan 16, 2017 at 16:02
• That is not going to be random. It will favor larger numbers for the last. It does not give 5,4 a chance versus 9. Jan 19, 2017 at 11:02

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
``````
• Let k = ceil (N / b) (that's the minimum number of items that you will need). If a·k ≤ N then there's a solution. b > 2a is not necessary if N is large enough, for example a = 10, b = 11, works if N ≥ 90. Jan 13, 2017 at 20:30
• I have mentioned in the question that a < b < N, so it is impossible to have N<a or N=a Jan 16, 2017 at 2:45

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.

• #3 looks like a very interesting approach. Imagine that we don't generate all possible variants outright, but can count them, and can generate them by its ordinal number. I suspect that a rather simple generation rule exists. Then we can just take a random ordinal and generate the corresponding combination.
– 9000
Jan 19, 2017 at 14:49

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)
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.

I think this will be random without starting over

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