number generator

[Steven D'Aprano]

On Fri, 09 Mar 2007 06:44:01 -0800, cesco wrote:

> I have to generate a list of N random numbers (integer) whose sum is
> equal to M. If, for example, I have to generate 5 random numbers whose
> sum is 50 a possible solution could be [3, 11, 7, 22, 7]. Is there a
> simple pattern or function in Python to accomplish that?

No, you'll have to program it yourself.

You might like to Google for the "coin change algorithm" for some hints on
how to accomplish this. It's not the same problem, but it might give you
some ideas on how to solve it.

The way to solve this problem also depends on what you mean by "random
numbers". For example, if the random numbers have to be uniformly
distributed (so that all numbers in the appropriate range are equally
likely to be picked), I think the only way to proceed is with the horribly
inefficient algorithm:

(1) Generate every possible list of N random numbers between 1 and the
maximum value allowed. If the maximum value is (say) 10, there will 10**N
such lists.

(2) Check each list's sum to see if it equals M, and eliminate it if it
doesn't.

That guarantees that the individual random numbers all have the same
probability, but the execution time will explode for large N.


If you relax the requirement that all the random numbers have the same
probability, you can use a heuristic that is biased towards picking
smaller numbers. E.g. something like this:

def make_sum(N, M):
    """Generate a random list of N ints that sum to M."""
    # WARNING: untested!

    def get_sum(M):
        # Returns a list of any length that sums to M.
        L = []
        while M > 0:
            n = random.randint(1, M)
            L.append(n)
            M -= n
        return L

    L = []
    while len(L) != N:
        L = get_sum(M)
    return L


This isn't a particularly good algorithm, since it will take a LONG time
to return a solution on average, but it should give you some clues towards
solving the problem more efficiently.

Another procedure might be to do something like the following:

We want to make a list of 5 numbers adding up to 50.
The first random number between 1 and 50 might be (say) 13.
So our list will consist of [13] plus a list of 4 numbers adding up to 37.
And so on...

There's a few subtleties which I'll leave to you.

Last but not least, another possible algorithm is to start with a list of
N numbers, regardless of whether or not they add to M, and then adjust
each one up or down by some amount until they sum to the correct value.



-- 
Steven.