High execution time on number partitioning program in Python 2.7

Question

I am writing a program to count only the partitions of a number with distinct parts. I am using a bottom-up approach to dynamic programming to generate partition lists from previously obtained partition lists. I think my program runs correctly, as I have tested for some inputs and verified from OEIS. But it's extremely slow for n>15. I think my algorithm has a complexity currently north of O(n^3), but I couldn't think of a better way to do it. Can anyone help with making it faster?

# Logic - The partition of a number 'n', will be 1 + the partition of 'n-1', 2 + the partition of 'n-2', and so on.
# So we start from 1, and build partition lists based on previously gotten partitions
# The loop doesn't have to go all the way till 1.
# For example, for 6, we only have to go till 'n-3' and stop, because after that, we only get duplicate lists. This is not to say that we don't get
# duplicates before, but after 'n-3', we get JUST duplicates
# So we only have to go till n-x >= x

from collections import Counter
compare = lambda x, y: Counter(x) == Counter(y)

def make_partitions(n):
    # Bottom up approach starts at 1 and goes till n, building on partitions already obtained

    # partitions dictionary contains list of lists of partitions
    # Ex - 1: [[1]]
    # Ex - 2: [[2], [1,1]]
    # Ex - 3: [[3], [2,1], [1,1,1]]
    partitions = {}
    start = 1
    while start <= n:
        partitions[start] = []
        # Appending the number itself as a partition of length 1
        partitions[start].append([start])

        # prev stores the number currently being used to build the partition list
        prev = start - 1
        # pp stores all partition lists obtained so far for the current number
        pp = []

        while prev >= start-prev:
            # curr_partitions stores the partition lists that make up the desired number, FROM the current number
            # Ex - for desired number 6, in first loop, it stores those lists which make up 6 from those of 5; in the second loop, from those of 4 and so on
            curr_partitions = []
            prev_partitions = partitions[prev]
            for p in prev_partitions:
                q = list(p)
                q.append(start-prev)

            # self-explanatory. compare function is used to see if the list already exists
            does_exist_already = False
            for ppp in pp:
                if compare(q, ppp):
                    does_exist_already = True
            if not does_exist_already:
                curr_partitions.append(q)

        # We have got the entire list of partitions that make up the desired number FROM the current number, so we add to the dictionary
        partitions[start].extend(curr_partitions)
        prev -= 1
        pp.extend(curr_partitions)
    start += 1
return partitions

def answer(n):
    partitions = make_partitions(n)
    req_partition_list = partitions[n]
    final_partition_list = []
    count = 0

    # This for loop is to weed out lists which contain duplicate values
    for p in req_partition_list:
        c = Counter(p)
        if all(v==1 for v in c.values()):
            final_partition_list.append(p)
            count += 1
    return count

if __name__ == '__main__':
    n = int(raw_input())
    print answer(n)

Answer 1

Indentation

Your code is indented using a mixture of spaces and newlines. In Python, the use of 4 spaces per indent level is preferred. While Python 2 allows for mixed indentation, PEP8 recommends these be converted to spaces exclusively. Your indentation format seems to have affected display of the following lines:

        partitions[start].extend(curr_partitions)
        prev -= 1
        pp.extend(curr_partitions)
    start += 1
return partitions

The resulting code does not run. I have cleaned up indentation for make_partitions:

from collections import Counter
compare = lambda x, y: Counter(x) == Counter(y)

def mp(n):
    partitions = {}
    curr_partitions = []
    start = 1
    while start <= n:
        partitions[start] = []
        partitions[start].append([start])
        prev = start - 1
        pp = []

        while prev >= start-prev:      
            curr_partitions = []
            prev_partitions = partitions[prev]
            for p in prev_partitions:
                q = list(p)
                q.append(start-prev)
            does_exist_already = False
            for ppp in pp:
                if compare(q, ppp):
                    does_exist_already = True
            if not does_exist_already:
                curr_partitions.append(q)

            partitions[start].extend(curr_partitions)
            prev -= 1
            pp.extend(curr_partitions)
        start += 1
    return partitions

Partitions

The edited code produces the following output for n = 7:

{1: [[1]], 2: [[2], [1, 1]], 3: [[3], [1, 1, 1]], 4: [[4], [1, 1, 1, 1],[1, 1,
2]], 5: [[5], [1, 1, 2, 1]], 6: [[6], [1, 1, 2, 1, 1], [1, 1, 2, 2], [1, 1, 1, 3
]], 7: [[7], [1, 1, 1, 3, 1], [1, 1, 2, 1, 2], [1, 1, 2, 3]]}

It seems that partitions containing integers in the range n/2 < i < n are not included. Then, it is hard to see how final_partition_list could contain the correct partitions. And, checking small values of n:

n = 3, output = 1

n = 4, output = 1

n = 5, output = 1

n = 6, output = 1

etc.

Your code may not necessarily be broken, but simply a victim of incorrect conversion from mixed indentation to spaces only.

Answer 2

Here are a few improvements:

partitions[start] = [] # Appending the number itself as a partition of length 1 
partitions[start].append([start]) 

Can be more succinctly written as:

partitions[start] = [[start]]

You should compute start - prev once and reuse it:

while 2*prev >= start:
    curr_partitions = []
    prev_partitions = partitions[prev]
    diff = start - prev
    for p in prev_partitions:
        p.append(diff)

Note that p should already be a list.

Your duplicate finding can be improved by breaking once a hit has been found:

does_exist_already = False
for ppp in pp:
    if compare(p, ppp):
        does_exist_already = True
        break
if not does_exist_already:
    curr_partitions.append(p)

Or, even better, use the short circuit evaluation of any:

if not any(compare(p, ppp) for ppp in pp):
    curr_partitions.append(p)

The weeding out of lists with duplicates can be sped-up using a set instead of collections.Counter:

for p in req_partition_list:
    if len(p) == len(set(p)):
        final_partition_list.append(p)
        count += 1

Finally, some stylistic remarks. Python has an official style-guide, PEP8, which programmers are encouraged to adhere to.

It recommends using a space before and after operators. It also encourages using easy to understand names for variables. p, pp, ppp and q are not easy to understand.