Velocity Reviews > number generator

# number generator

cesco
Guest
Posts: n/a

 03-09-2007
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?

Thanks and regards
Francesco

Paul Rubin
Guest
Posts: n/a

 03-09-2007
"cesco" <(E-Mail Removed)> writes:
> 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?

Erm, yes, lots of ways, there are probably further constraints on the
problem, such as the size of the integers, how the lists are supposed
to be distributed, etc. Can you be more specific? Is this for an
application? If it's a homework problem, that's fine, but it's better
in that case for respondents to suggest hints rather than full solutions.

cesco
Guest
Posts: n/a

 03-09-2007
On Mar 9, 3:51 pm, Paul Rubin <http://(E-Mail Removed)> wrote:
> "cesco" <(E-Mail Removed)> writes:
> > 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?

>
> Erm, yes, lots of ways, there are probably further constraints on the
> problem, such as the size of the integers, how the lists are supposed
> to be distributed, etc. Can you be more specific? Is this for an
> application? If it's a homework problem, that's fine, but it's better
> in that case for respondents to suggest hints rather than full solutions.

Given two positive integers, N and M with N < M, I have to generate N
positive integers such that sum(N)=M. No more constraints.

Thanks again
Francesco

Marc 'BlackJack' Rintsch
Guest
Posts: n/a

 03-09-2007
In <(E-Mail Removed) .com>, cesco wrote:

> Given two positive integers, N and M with N < M, I have to generate N
> positive integers such that sum(N)=M. No more constraints.

Break it into subproblems. Generate a random number X from a suitable
range and you are left with one number, and the problem to generate (N-1)
random numbers that add up to (M-X). You have to think a little bit about
the "suitable range" part though.

The necessary functions to draw random numbers are in the `random` module.

Ciao,
Marc 'BlackJack' Rintsch

Gerard Flanagan
Guest
Posts: n/a

 03-09-2007
On Mar 9, 4:17 pm, "cesco" <(E-Mail Removed)> wrote:
> On Mar 9, 3:51 pm, Paul Rubin <http://(E-Mail Removed)> wrote:
>
> > "cesco" <(E-Mail Removed)> writes:
> > > 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?

>
> > Erm, yes, lots of ways, there are probably further constraints on the
> > problem, such as the size of the integers, how the lists are supposed
> > to be distributed, etc. Can you be more specific? Is this for an
> > application? If it's a homework problem, that's fine, but it's better
> > in that case for respondents to suggest hints rather than full solutions.

>
> Given two positive integers, N and M with N < M, I have to generate N
> positive integers such that sum(N)=M. No more constraints.
>
> Thanks again
> Francesco

Suppose you have a fixed telegraph pole at N and a fixed telgraph pole
at M, and you're given 5 more telegraph poles...

Carsten Haese
Guest
Posts: n/a

 03-09-2007
On Fri, 2007-03-09 at 07:17 -0800, cesco wrote:
> On Mar 9, 3:51 pm, Paul Rubin <http://(E-Mail Removed)> wrote:
> > "cesco" <(E-Mail Removed)> writes:
> > > 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?

> >
> > Erm, yes, lots of ways, there are probably further constraints on the
> > problem, such as the size of the integers, how the lists are supposed
> > to be distributed, etc. Can you be more specific? Is this for an
> > application? If it's a homework problem, that's fine, but it's better
> > in that case for respondents to suggest hints rather than full solutions.

>
> Given two positive integers, N and M with N < M, I have to generate N
> positive integers such that sum(N)=M. No more constraints.

Paul still had a point, since the word "positive" is a vital piece of
information that never appeared in your original description.

-Carsten

Paul Rubin
Guest
Posts: n/a

 03-09-2007
Carsten Haese <(E-Mail Removed)> writes:
> > Given two positive integers, N and M with N < M, I have to generate N
> > positive integers such that sum(N)=M. No more constraints.

> Paul still had a point, since the word "positive" is a vital piece of
> information that never appeared in your original description.

It's maybe even more complicated that way. Does the OP want to
generate each possible partition with equal probability? See

http://en.wikipedia.org/wiki/Partition_number

Bjoern Schliessmann
Guest
Posts: n/a

 03-09-2007
cesco wrote:
> On Mar 9, 3:51 pm, Paul Rubin <http://(E-Mail Removed)>
>> "cesco" <(E-Mail Removed)> writes:
>>> 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?

Isn't at least one of those numbers depending on the others?

> Given two positive integers, N and M with N < M, I have to
> generate N positive integers such that sum(N)=M. No more
> constraints.

Then why must they be random? div and mod should do it.

Regards,

Björn

--
BOFH excuse #220:

Someone thought The Big Red Button was a light switch.

Steven D'Aprano
Guest
Posts: n/a

 03-09-2007
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.

Dennis Lee Bieber
Guest
Posts: n/a

 03-09-2007
On 9 Mar 2007 06:44:01 -0800, "cesco" <(E-Mail Removed)> declaimed
the following in comp.lang.python:

> 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?
>

Well... Just that the last number is not random -- it has to equal
(using your limit of 50 and 5 numbers):

fifth = 50 - sum(first, second, third, fourth)

Assuming that 0 is NOT allowed, this means that their is a
constraint that

sum(first, second, third, fourth) < 50

(and I presume all are integer)

Furthermore, presuming repeated values are permitted (as in your
example)

first < (50 - 4)

as the worst case is

second = third = fourth = fifth = 1

Repeat the algorithm for each remainder....
--
Wulfraed Dennis Lee Bieber KD6MOG
http://www.velocityreviews.com/forums/(E-Mail Removed) (E-Mail Removed)
HTTP://wlfraed.home.netcom.com/
(Bestiaria Support Staff: (E-Mail Removed))
HTTP://www.bestiaria.com/