5

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. – CodesInChaos Jan 13 '17 at 10:53
  • You say that you want to generate sets, but the sample outputs contain duplicates. – CodesInChaos Jan 13 '17 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? – cytsunny Jan 13 '17 at 10:56
  • 1
    The big problem: Define "random". – gnasher729 Jan 16 '17 at 16:02
  • 1
    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. – paparazzo Jan 19 '17 at 11:02
3

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. – gnasher729 Jan 13 '17 at 20:30
  • I have mentioned in the question that a < b < N, so it is impossible to have N<a or N=a – cytsunny Jan 16 '17 at 2:45
3

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 '17 at 14:49
1

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.

1

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);
}

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.