Divide the number into random number of random elements?

Question

If I need to divide for example 7 into random number of elements of random size, how would I do this?

So that sometimes I would get [3,4], sometimes [2,3,1] and sometimes [2,2,1,1,0,1]?

I guess it's quite simple, but I can't seem to get the results. Here what I am trying to do code-wise (does not work):

def split_big_num(num):
    partition = randint(1,int(4))
    piece = randint(1,int(num))
    result = []
    for i in range(partition):
        element = num-piece
        result.append(element)
        piece = randint(0,element)
#What's next?
        if num - piece == 0:
            return result
    return result

EDIT: Each of the resulting numbers should be less than initial number and the number of zeroes should be no less than number of partitions.

Specify what you mean by random number of elements. Do you mean every length of subset has the same probability of being picked? Or do you mean that every subset has the same probability of being picked? Those mean very different things. — David Robinson, Apr 24 '12 at 20:14
Should it ever return [7]? What about [0,0,0,0,0,7]? Are they possible? — DanRedux, Apr 24 '12 at 20:15
wow, great question! Yes, no more than the number of partitions.. — Stpn, Apr 24 '12 at 20:18
try the concepts of permutation and combinations , to get all the possible combinations. — Ashwini Chaudhary, Apr 24 '12 at 20:19
A problem that people too often have is to state they want a random number of (something), but then they fail to say what is the distribution. Without knowledge of the distribution, randomness is an unanswerable goal. — , Apr 24 '12 at 22:48

score 13 · Accepted Answer · answered Apr 24 '12 at 20:19

13

I'd go for the next:

>>> def decomposition(i):
        while i > 0:
            n = random.randint(1, i)
            yield n
            i -= n

>>> list(decomposition(7))
[2, 4, 1]
>>> list(decomposition(7))
[2, 1, 3, 1]
>>> list(decomposition(7))
[3, 1, 3]
>>> list(decomposition(7))
[6, 1]
>>> list(decomposition(7))
[5, 1, 1]

However, I am not sure if this random distribution is perfectly uniform.

answered Apr 24 '12 at 20:19

Roman Bodnarchuk

29,461
12
59
75

Great! Thanks a lot! I will accept this as an answer as soon as SO allows. – Stpn Apr 24 '12 at 20:20
Nice answer! Minor Point: using `n = rn.randint(0, i)` would allow zeros that Stpn wanted. – Akavall Apr 24 '12 at 20:26
@Akavall: And also allow it to start accumulating a lot of 0s. – Gareth Latty Apr 24 '12 at 20:27
This violates the requirements by allowing 7 to be returned. – ninjagecko Apr 24 '12 at 20:42
1

OK, I misread that part, but he does have a zero in his example, but dealing with this that is probably just details. – Akavall Apr 24 '12 at 20:50
6

This distribution is very, very far from being perfectly uniform. You tend to have far too many big numbers, and they tend to appear at the start. – btilly Apr 24 '12 at 21:50

score 4 · Answer 2 · edited May 23 '17 at 11:51

You have to define what you mean by "random". If you want an arbitrary integer partition, you can generate all integer partitions, and use random.choice. See python: Generating integer partitions This would give no results with 0. If you allow 0, you will have to allow results with a potentially infinite number of 0s.

Alternatively if you just want to take random chunks off, do this:

def arbitraryPartitionLessThan(n):
    """Returns an arbitrary non-random partition where no number is >=n"""
    while n>0:
        x = random.randrange(1,n) if n!=1 else 1
        yield x
        n -= x

It is slightly awkward due to the problem constraints that each number should be less than the original number; it would be more elegant if you allowed the original number. You can do randrange(n) if you want 0s but it wouldn't make sense unless there is a hidden reason you are not sharing.

edit in response to question edit: Since you desire the "the number of zeroes should be no less than number of partitions" you can arbitrarily add 0s to the end:

def potentiallyInfiniteCopies(x):
    while random.random()<0.5:
        yield x

x = list(arbitraryPartitionLessThan(n))
x += [0]*len(x) + list(potentiallyInfiniteCopies(0))

The question is quite arbitrary, and I highly recommend that you choose this instead as your answer:

def arbitraryPartition(n):
    """Returns an arbitrary non-random partition"""
    while n>0:
        x = random.randrange(1,n+1)
        yield x
        n -= x

The number of compositions grows exponentially quickly. Thus even a modest value of n can use up all of your memory. — btilly, Apr 24 '12 at 21:51

score 1 · Answer 3 · answered Apr 24 '12 at 20:20

1

Recursion to the rescue:

import random

def splitnum(num, lst=[]):
    if num == 0:
        return lst
    n = random.randint(0, num)
    return splitnum(num - n, lst + [n])

for i in range(10):
    print splitnum(7)

Result:

[1, 6]
[6, 0, 0, 1]
[5, 1, 1]
[6, 0, 1]
[2, 0, 3, 1, 1]
[7]
[2, 1, 0, 4]
[7]
[3, 4]
[2, 0, 4, 1]

answered Apr 24 '12 at 20:20

Israel Unterman

13,158
4
28
35

@AshwiniChaudhary: calculate the odds of that sequence being returned, and there's your answer. – Wooble Apr 24 '12 at 22:33

score 0 · Answer 4 · answered Apr 24 '12 at 22:02

This solution does not insert 0s (I do not understand what your description of your zeros rule is supposed to be), and is equally likely to generate every possible combination other than the original number by itself.

def split (n):
    answer = [1]
    for i in range(n - 1):
        if random.random() < 0.5:
            answer[-1] += 1
        else:
            answer.append(1)

    if answer == [n]:
        return split(n)
    else:
        return answer

Divide the number into random number of random elements?

4 Answers4