How can I modify this function to count the average length of a partition of a number?

Question

I am working with partitions (number theory). I want to write a function that will tell me the average length of the partitions of a number. For example. The partitions of the number 4 are:

1+1+1+1
1+1+2
1+3
2+2
4

I borrowed this function from another question on here, which prints you all of the ways to add a list of numbers to a given number:

def subset_sum(numbers, target, partial=[]):
    s = sum(partial)

# check if the partial sum is equals to target
    if s == target:
        print "sum(%s)=%s" % (partial, target)
    if s >= target:
        return  # if we reach the number why bother to continue

    for i in range(len(numbers)):
        n = numbers[i]
        remaining = numbers[i+1:]
        subset_sum(remaining, target, partial + [n])

if __name__ == "__main__":
    subset_sum([1,2,3,4,5,6,7,8,9,10,11,12,13,14,15],15)

Outputs:

sum([3, 8, 4])=15
sum([3, 5, 7])=15
sum([8, 7])=15
sum([5, 10])=15

And I modified it to allow for repeats by changing:

remaining = numbers[i+1:]

to:

remaining = numbers[i:]

Then I added two parameters to the function:

def subset_sum(numbers, target, length_twos=[0], partitions_with_twos=[0],
               partial=[]):

and I added inside the function to say:

if s == target:
    if 2 in partial:
        length_twos[0]+=len(partial)
        partitions_with_twos[0]+=1

Then at the end I wanted to find out the average length of partitions that contained a 2 was. But it's not giving me the right answer. Any idea why? For example, the average for the number 4 should be 2.5.

Of course I also modified the subset_sum() within the function to include the parameters recursively. Like so.

for i in range(len(numbers)):
    n = numbers[i]
    remaining = numbers[i+1:]
    subset_sum(remaining, target, length_twos, partitions_with_twos,
               partial + [n])

I don't get the result you say you do using the unmodified function you "borrowed". Rather than just describing in words the changes you made, it would be more useful to see the actually non-working code along with a more detailed description than "But it's not giving me the right answer" and well as an indication of what the "right answer" is. Beside all of that, why do the modifications only target lengths of 2 when you say want to average of _all_ lengths? — martineau, Sep 06 '17 at 16:13

Martin Evans · Answer 1 · 2017-09-06T17:09:35.403

Using this excellent partition generator by @skovorodkin, a list of the lengths can be created. From this, the average length can be calculated:

def partitions(n, I=1):
    yield (n,)
    for i in range(I, n//2 + 1):
        for p in partitions(n-i, i):
            yield (i,) + p

partition_lengths = [len(p) for p in partitions(4) if 2 in p]

print partition_lengths
print sum(partition_lengths) / float(len(partition_lengths))

Giving you the following output for 4:

[3, 2]
2.5

Where the partitions generated with 2 in would be:

[(1, 1, 2), (2, 2)]

score 0 · Answer 2 · answered Sep 06 '17 at 19:53

As I said, I don't really understand your question. That said, perhaps you'll find the following snippet of code useful:

def partition(n):
    """ Find partitions of integer 'n'.
        Simplification of https://stackoverflow.com/a/400796/355230
    """
    result = [[n]]

    for i in range(1, n):
        a = n-i
        for r in partition(i):
            if r[0] <= a:
                result.append([a] + r)

    return result

def subset_sum(target):
    """ Find average length of partitions of the target integer. """
    numbers = partition(target)
    return sum(map(len, numbers)) / float(len(numbers))

if __name__ == "__main__":
    target = 4
    numbers = partition(target)  # computed and printed here only for testing
    print('partitions of {}: {}'.format(target, numbers))
    print('average length of partitions: {}'.format(subset_sum(target)))

Output:

partitions of 4: [[4], [3, 1], [2, 2], [2, 1, 1], [1, 1, 1, 1]]
average length of partitions: 2.4

How can I modify this function to count the average length of a partition of a number?

2 Answers2