Speed up this python script that prints all UNIQUE partitions of a number in python

Question

This code is doing a lot of unnecessary processing. For ex, for the number 3, one of its partitions is 1+1+1, but it keeps finding '1+1+1's even after the first one. There are a total of 6. How to stop it after the first one?

def perm(a,k=0):
    if k==len(a):
        permstr=''
        for i in range(len(a)):
            permstr=permstr+str(a[i])
        if int(permstr) not in permslist:
            permslist.append(int(permstr))
    else:
        for i in range(k,len(a)):
            a[k],a[i] =a[i],a[k]
            perm(a,k+1)
            a[k],a[i] =a[i],a[k]
         
def sumways(n,size,limit):
    if limit is None:
        limit=n
    if size==1:
        if n<=limit:
            yield[n]
    else:
        for i in range(0,limit+1):
            for tail in sumways(n-i,size-1,min(i,n-i)):
                yield[i]+tail

m=11
for n in range(1,1+m):
    permslist=[]
    sums=list(sumways(n,n,n))
    for i in range(len(sums)):
        sums[i]=[j for j in sums[i] if j!=0]
        if perm(sums[i])!=None:
            perm=(perm(sums[i]))
    maxave=0
    for i in range(len(permslist)):
        ave=0
        for j in range(len(str(permslist[i]))):
            ave=ave+int(str(permslist[i])[j])
        ave=ave/(1+j)
        if ave>maxave:
            maxave=ave
            maxaveat=permslist[i]
    print(n,len(permslist),maxave,maxaveat,permslist)
    print()

Answer 1

You can just use the "stars and bars" approach to partition a number.

For example, m = 3:

1 + 1 + 1
  |   |         <- possible positions of a bar

A bar (which splits up the partition) is placed if a binary bit is 1, otherwise omitted. So, you just count up to 11b (which is 2^(m-1)-1) in binary to get all the partitions without any repetition.

This assumes that 1+2 is different from 2+1, for example.

m = int( input( "Enter m: " ) )
for p in range( 1 << ( m - 1 ) ):      # count to 2^(m-1)-1 in binary
    a = 1
    for pos in range( m - 1 ):
        if p & ( 1 << pos ):           # actually, reverse binary: not that it matters
            print( a, end='+' )
            a = 1
        else:
            a += 1
    print( a )

e.g. for m = 3

Enter m: 3
3
1+2
2+1
1+1+1