number generator

Discussion in 'Python' started by cesco, Mar 9, 2007.

  1. cesco

    cesco Guest

    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
    cesco, Mar 9, 2007
    #1
    1. Advertising

  2. cesco

    Paul Rubin Guest

    "cesco" <> 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.
    Paul Rubin, Mar 9, 2007
    #2
    1. Advertising

  3. cesco

    cesco Guest

    On Mar 9, 3:51 pm, Paul Rubin <http://> wrote:
    > "cesco" <> 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
    cesco, Mar 9, 2007
    #3
  4. In <>, 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
    Marc 'BlackJack' Rintsch, Mar 9, 2007
    #4
  5. On Mar 9, 4:17 pm, "cesco" <> wrote:
    > On Mar 9, 3:51 pm, Paul Rubin <http://> wrote:
    >
    > > "cesco" <> 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...
    Gerard Flanagan, Mar 9, 2007
    #5
  6. On Fri, 2007-03-09 at 07:17 -0800, cesco wrote:
    > On Mar 9, 3:51 pm, Paul Rubin <http://> wrote:
    > > "cesco" <> 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
    Carsten Haese, Mar 9, 2007
    #6
  7. cesco

    Paul Rubin Guest

    Carsten Haese <> 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

    for more info.
    Paul Rubin, Mar 9, 2007
    #7
  8. cesco wrote:
    > On Mar 9, 3:51 pm, Paul Rubin <http://>
    >> "cesco" <> 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.
    Bjoern Schliessmann, Mar 9, 2007
    #8
  9. 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.
    Steven D'Aprano, Mar 9, 2007
    #9
  10. On 9 Mar 2007 06:44:01 -0800, "cesco" <> 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://wlfraed.home.netcom.com/
    (Bestiaria Support Staff: )
    HTTP://www.bestiaria.com/
    Dennis Lee Bieber, Mar 9, 2007
    #10
  11. On Fri, 09 Mar 2007 18:41:39 GMT, Dennis Lee Bieber
    <> declaimed the following in comp.lang.python:


    >
    > Repeat the algorithm for each remainder....


    And just to add incentive -- if one packs the code tightly, it can
    be done in five lines, non-recursively, including the "def" and "return"
    (but not counting the "import random").

    I got expansive, however, and added a docstring, two assertions, and
    split the main computation over three lines. And then added 23 lines of
    test cases (including the "if __name__ ==..." line.

    Output from a run (list of numbers generated, sum):

    [32, 8, 4, 4, 2] 50
    [35, 8, 3, 1, 3] 50
    [1, 7, 26, 6, 5, 1, 1, 1, 1, 1] 50
    Must have at least one return value: 0 > 0 failed
    Must have at least one return value: -2 > 0 failed
    Can not return 10 values that sum to less than 10: 9 >= 10 failed
    [1, 1, 1, 1, 1] 5
    [50] 50

    Note that the last two are pathological cases... 5 "random" integers
    that add up to "5" can only be a sequence of 5 1s. 1 "random" integer
    that adds up to "50" can only be a sequence of a single "50".

    A second run...

    [31, 4, 5, 4, 6] 50
    [11, 11, 12, 4, 12] 50
    [41, 1, 1, 1, 1, 1, 1, 1, 1, 1] 50
    Must have at least one return value: 0 > 0 failed
    Must have at least one return value: -2 > 0 failed
    Can not return 10 values that sum to less than 10: 9 >= 10 failed
    [1, 1, 1, 1, 1] 5
    [50] 50

    which shows that not all the big numbers come first (note the second
    line). {Also note how the third line, after the first random value,
    devolved into a pathological case...}

    --
    Wulfraed Dennis Lee Bieber KD6MOG

    HTTP://wlfraed.home.netcom.com/
    (Bestiaria Support Staff: )
    HTTP://www.bestiaria.com/
    Dennis Lee Bieber, Mar 10, 2007
    #11
  12. On Mar 9, 7:32 am, Marc 'BlackJack' Rintsch <> wrote:
    > In <>, 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).


    This approach skews the probabilities. The OP said for example with
    N=5 and M=50 that a possible solution is [3, 11, 7, 22, 7]. You're
    approach biases the probabilities toward solutions that have a large
    entry in the first position.

    To make the solutions equi-probable, a simple approach is to
    recursively enumerate all possibilities and then choose one of them
    with random.choice().


    Raymond
    Raymond Hettinger, Mar 10, 2007
    #12
  13. In <>, Raymond
    Hettinger wrote:

    > On Mar 9, 7:32 am, Marc 'BlackJack' Rintsch <> wrote:
    >> In <>, 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).

    >
    > This approach skews the probabilities. The OP said for example with
    > N=5 and M=50 that a possible solution is [3, 11, 7, 22, 7]. You're
    > approach biases the probabilities toward solutions that have a large
    > entry in the first position.


    I know but he said also "No more constraints". And…

    > To make the solutions equi-probable, a simple approach is to
    > recursively enumerate all possibilities and then choose one of them
    > with random.choice().


    …it would be faster than creating all possibilities. :)

    Ciao,
    Marc 'BlackJack' Rintsch
    Marc 'BlackJack' Rintsch, Mar 10, 2007
    #13
  14. cesco

    greg Guest

    Steven D'Aprano wrote:

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


    Another possibility is to generate a list of N non-random
    numbers that sum to M, and then adjust them up or down
    by random amounts. By performing up/down adjustments in
    pairs, you can maintain the sum invariant at each step.
    So then it's just a matter of how long you want to go
    on fiddling with them.

    --
    Greg
    greg, Mar 10, 2007
    #14
  15. Raymond Hettinger wrote:

    > To make the solutions equi-probable, a simple approach is to
    > recursively enumerate all possibilities and then choose one
    > of them with random.choice().


    Or create a list using the biased method, then use .shuffle() to
    return another permutation.

    Cheers,

    --
    Klaus Alexander Seistrup
    Tv-fri medielicensbetaler
    http://klaus.seistrup.dk/
    Klaus Alexander Seistrup, Mar 10, 2007
    #15
  16. cesco

    Dick Moores Guest

    At 07:17 AM 3/9/2007, cesco wrote:
    >On Mar 9, 3:51 pm, Paul Rubin <http://> wrote:
    > > "cesco" <> 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.


    So why not just repeatedly call a function to generate lists of
    length N of random integers within the appropriate range (the closed
    interval [1,M-N-1]), and return the first list the sum of which is M?
    I don't understand what all the discussion is about. Time is not one
    of the constraints.

    Dick Moores
    Dick Moores, Mar 10, 2007
    #16
  17. On Sat, 10 Mar 2007 02:32:21 -0800, Dick Moores wrote:

    > So why not just repeatedly call a function to generate lists of
    > length N of random integers within the appropriate range (the closed
    > interval [1,M-N-1]), and return the first list the sum of which is M?
    > I don't understand what all the discussion is about. Time is not one
    > of the constraints.


    Time is always a constraint. The sun will expand and destroy the Earth in
    a couple of billion years, it would be nice to have a solutions before
    then...

    *wink*

    Seriously, almost all programming problems have two implicit constraints:
    it must run as fast as practical, using as little computer resources (e.g.
    memory) as practical. Naturally those two constraints are usually in
    opposition, which leads to compromise algorithms that run "fast enough"
    without using "too much" memory.



    --
    Steven.
    Steven D'Aprano, Mar 10, 2007
    #17
  18. On Fri, 09 Mar 2007 18:41:39 +0000, Dennis Lee Bieber wrote:

    > On 9 Mar 2007 06:44:01 -0800, "cesco" <> 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)


    Doesn't mean that it isn't random. After all, the first four numbers are
    random, therefore their sum is random. 50 - (something random) is also
    random.

    In practice, one would deterministically generate the last number needed,
    but that last number is unpredictable because the first four numbers are
    unpredictable.

    Remember that random numbers are not necessarily unconstrained, nor are
    they necessarily uniformly distributed. We blithely talk about "random
    numbers", but of course there is a constraint that we're selecting from a
    finite range. Any finite range of numbers, no matter how big, is a
    vanishingly small percentage of all the possible numbers.



    --
    Steven.
    Steven D'Aprano, Mar 10, 2007
    #18
  19. Raymond Hettinger wrote:

    > To make the solutions equi-probable, a simple approach is to
    > recursively enumerate all possibilities and then choose one of them
    > with random.choice().


    Maybe it is possible to generate the possibilities by an indexing
    function and then use randint to pick one of them. I suppose this is
    like the bricks and bins problem this thread was about:

    http://groups.google.nl/group/comp.lang.python/browse_thread/thread/4782b54fa39b3bad

    Except that the bins now have at least 1 brick in them (if we have
    positive numbers).

    I posted a rather simplistic solution (but working I think) after Steven
    Taschuk made some insightful remarks. I believe it is possible to
    generate the list of numbers directly instead of permuting a list of '0'
    and '1' characters and then finding the positions of the '1' elements.

    A.
    Anton Vredegoor, Mar 10, 2007
    #19
  20. cesco

    Paul Rubin Guest

    Steven D'Aprano <> writes:
    > Doesn't mean that it isn't random. After all, the first four numbers are
    > random, therefore their sum is random. 50 - (something random) is also
    > random.


    What does it mean for the first 4 numbers to be random? For example,
    is 27 random?

    By your method, what is the probability of the first number being
    higher than 30? What is the probability of the fifth number being
    higher than 30? If these probabilities are unequal, can we really say
    the sequences are random?
    Paul Rubin, Mar 10, 2007
    #20
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Martin Maurer
    Replies:
    3
    Views:
    4,770
    Peter
    Apr 19, 2006
  2. TheDustbustr
    Replies:
    1
    Views:
    430
    Sami Hangaslammi
    Jul 25, 2003
  3. Replies:
    9
    Views:
    524
  4. Chris Withers

    Problems with email.Generator.Generator

    Chris Withers, Sep 11, 2006, in forum: Python
    Replies:
    20
    Views:
    1,666
    Max M
    Sep 12, 2006
  5. Terry Reedy

    Generator functions subclass generator?

    Terry Reedy, Jun 18, 2009, in forum: Python
    Replies:
    0
    Views:
    444
    Terry Reedy
    Jun 18, 2009
Loading...

Share This Page