Python整数分区

Question

我想写一段代码，它会给我一个数字的分区。到目前为止，我想出了这个（在谷歌上找到）。

def gen(n): 
      # tuple version 
      if n == 0: 
       yield() 
       return 

      for p in gen(n-1): 
       yield (1,) + p 
       if p and (len(p)<2 or p[1] > p[0]): 
        yield (p[0] + 1,) + p[1:] 

print(list(gen(5))) 

我真的很感激，如果有人能帮助我理解这个递归函数是如何工作的，请帮助。谢谢。

Answer 1

yield将您的功能变成发电机。请阅读this answer以获得很好的解释。

基本上，而不是创造一次结果的列表，然后再返回它：

def f(): 
    output = [] 

    for i in range(10): 
     output.append(i + 3) 

    return output 

您可以创建一个生成器，yield的项目进行仅当您请求之一：

def f(): 
    for i in range(10): 
     yield i + 3 

这是也可以制造无限发电机：

def f(): 
    a = 0 
    b = 1 

    while True: 
     yield b 

     a, b = b, a + b 

在01上进行迭代将继续吐出Fibonacci序列的条款。

Answer 2

要理解这是怎么回事，它有助于打印发电机的输出的n多个依次增加的值：

>>> for i in range(5): 
     print(list(gen(i))) 

[()] 
[(1,)] 
[(1, 1), (2,)] 
[(1, 1, 1), (1, 2), (3,)] 
[(1, 1, 1, 1), (1, 1, 2), (2, 2), (1, 3), (4,)] 

每个序列的计算是基于之前的一个。下面是它如何工作的行一行解释：

if n == 0: 
    yield() 
    return 

发电机的这些前几行是基本情况，其中n为零。 return语句使得它在产生空元组之后退出，而不是继续执行其余的代码。

for p in gen(n-1): 

这是该函数的递归步骤。由于gen是一个生成器，因此它是用一个循环完成的，所以其余代码将重复运行，p从递归结果中获取不同的值。

yield (1,) + p 

这是一条重要的线。这样做是通过将一个1连接到值p的前面形成的新元组产生出发生器。如果p是空元组，这将是一个1元组。如果p已经有一些值，则元组将变长。

if p and (len(p)<2 or p[1] > p[0]): 

这是一个复杂的条件。第二个检查len(p)<2确实可以写成len(p)==1，因为p and部分在开始时已经排除了p为空。

p可以有两种值，以通过。 p只有一个值，或者它有更多的值，其第一个值小于第二个值。所以(3,)会通过，如(1,2)，但(1,1,1)不会。

 yield (p[0] + 1,) + p[1:] 

这是另一个元组连接。它将p的第一个值增加1，然后将其与p的其余部分（使用切片）连接起来。所以(3,)将成为(4,)（具有层为空），(1,2)变得(2,2)等

所以，现在让我们通过我们上面看到运行结果。

[()] 

随着n等于0时，基本情况被击中，你会得到一个空的元组产生。

[(1,)] 

随着n等于1，则循环运行一次，并连接(1,)到空的元组，产生1元组(1,)。 if条件的第一部分未通过，因为p为空。

[(1,1), (2,)] 

随着n等于2，循环仍然只运行一次。首先通过连接(1,)与其自身得到(1,1)得到(1,1)。但是这一次，if块被运行，因为p只有一个值。所以它也产生(p[0]+1,) + p[1:]。该片的部分是空元组，但第一部分是(2,)。

[(1,1,1), (1,2), (3,)] 

现在终于循环得到运行不止一次！但是，它第一次将(1,)连接到(1,1)的前面，并且由于if声明的条件未得到满足，这就是它的全部。然而，在第二次通过时，它产生两个值，一旦连接(1,)和(2,)，然后将(2,)递增到(3,)。

[(1, 1, 1, 1), (1, 1, 2), (2, 2), (1, 3), (4,)] 

这一个我会留给你，走过去。就像上面的情况一样，p将采用来自上一级调用（(1,1,1), (1,2), (3,)）的每个值，对于每个值，它将产生一个或两个新结果。