加速这个在 python 中打印数字的所有唯一分区的 python 脚本

Question

这段代码做了很多不必要的处理。例如，对于数字 3，它的一个分区是 1+1+1，但即使在第一个分区之后，它仍然不断查找“1+1+1”。一共6个，第一个之后如何停止？

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

您可以使用“星形和条形”的方法来划分数字。

例如，m = 3：

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

如果二进制位为 1，则放置一个条（分隔分区），否则省略。因此，您只需以二进制数数到 11b（即 2^(m-1)-1）即可获得所有分区，无需任何重复。

例如，假设 1+2 与 2+1 不同。

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

例如对于 m = 3

Enter n: 3
3
1+2
2+1
1+1+1