在Python中分割数字的方法数量 [英] Number of ways to partition a number in Python

问题描述

我定义了一个递归函数，该函数采用一个数字n，并返回一个与该数字(分区)相加的数字列表的list:

I have defined a recursive function that takes a number, n, and returns a list of lists of the numbers that sum to that number (partitions):

def P(n):
    # base case of recursion: zero is the sum of the empty list
    if n == 0:
        yield []
        return

    for p in P(n-1):        
        p.append(1)
        yield p
        p.pop()
        if p and (len(p) < 2 or p[-2] > p[-1]):
            p[-1] += 1
            yield p

我想知道如何使函数返回数字n的分区的数字.

I was wondering how to make the function return the number of partitions for number n.

例如，P(6)将返回10.

推荐答案

如果您查看

If you look at the "Partition function formulas" section of the Partiton (number theory) page on Wikipedia, you'll see that there isn't a simple way to find the partition number.

相反，您最好的选择可能是:

Instead, your best bet is probably:

sum(1 for _ in P(6))

或者稍微简单一些，但占用大量内存

or, slightly simpler but memory hogging for large numbers

len(list(P(6)))

使用现有功能.

还请注意，如果您希望能够保存P返回的值，则应该yield ing p[:]而不是p-您要进行复制，而不要产生相同的列表(一遍又一遍地更改).您会看到为什么要执行list(P(6))的原因-它会返回一遍又一遍地重复的相同空列表的列表.

Also note if you want to be able to save the values returned by P, you should be yielding p[:] not p -- you want to make a copy, not yield the same list (which you change) over and over. You can see why if you do list(P(6)) -- it returns a list of the same empty list repeated over and over.

有关分区的更多信息，请参见使用Python进行分区.

Fore more info about partitioning, see Partitioning with Python.

这篇关于在Python中分割数字的方法数量的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！