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.

Answer 1

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.

Answer 2

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