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. -- http://mail.python.org/mailman/listinfo/python-list