High execution time on number partitioning program in Python 2.7 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&gt;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 &gt;= 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 &lt;= 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 &gt;= 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)
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 &lt;= n:
        partitions[start] = []
        partitions[start].append([start])
        prev = start - 1
        pp = []

        while prev &gt;= 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 &lt; i &lt; 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.