2015-10-20 66 views
0

我想创建n个项目的所有可能的分布。这是指通常已知的鸽子原理。Python:递归创建条件列表的列表

下面的值是Microsoft Excel中的结果:

get_distributions(list, number_of_items_to_distribute) 
get_distributions([], 1) = [[1]] 
get_distributions([], 2) = [[1, 1], [2]] 
get_distributions([], 3) = [[1, 1, 1], [1, 2], [2, 1], [3]] 
get_distributions([], 4) = [[1, 1, 1, 1], [1, 1, 2], [1, 2, 1], [1, 3], [2, 1, 1], [2, 2], [3, 1], [4]] 

我已经有一些代码,但也有一些问题,删除临时表。使用此功能,我可以在“end:”后打印出好的结果,但某些值(如[1,2](调用n = 3))缺失。除此之外,这些值不会附加到我的all_distribution。

我很感兴趣的方式,我试图解决这个问题。这是一个好方法还是我绝对错了?

+0

什么呢明确方法?列表没有这个属性 –

+0

@PasqualGuerrero:在Python 3中存在'clear'方法。https://docs.python.org/3/tutorial/datastructures.html –

回答

1

您的代码的主要问题是,列表all_distributions最终包含许多对同一输入列表distribution的引用。当您拨打all_distributions.append(distribution)时,列表distribution未被复制到列表all_distributions中,但仅添加对该列表的引用。 all_distributions.append(list(distribution))

的最小修复你的代码是插入的副本,在基本情况下删除​​,和递归调用后加入distribution.pop()

all_distributions = [] 

def get_distributions(distribution, items): 
    if items == 0: 
     all_distributions.append(list(distribution)) 
    else: 
     for i in range(1, items + 1): 
      distribution.append(i) 
      get_distributions(distribution, items - i) 
      distribution.pop() 

get_distributions([], 3) 
print(all_distributions) 

输出您可以通过显式地将副本解决这个问题: [[1, 1, 1], [1, 2], [2, 1], [3]]


一个更好的办法是避免使用distribution.append,而是使用加运算的名单,像这样:

def get_distributions(distribution, items): 
    if items == 0: 
     all_distributions.append(distribution) 
    else: 
     for i in range(1, items + 1): 
      d = distribution + [i] 
      get_distributions(d, items - i) 

列表上的加号运算符通过连接两个给定列表来创建一个新列表。在这种情况下,我们将连接distribution右侧的单个元素i以获取包含distribution后跟i中的元素的新副本。


另一项改进是避免全局变量all_distributions,而是返回分布的名单:

def get_distributions(distribution, items): 
    if items == 0: 
     return [distribution] 
    else: 
     all_distributions = [] 
     for i in range(1, items + 1): 
      d = distribution + [i] 
      all_distributions += get_distributions(d, items - i) 
     return all_distributions 

print(get_distributions([], 4)) 

输出:[[1, 1, 1, 1], [1, 1, 2], [1, 2, 1], [1, 3], [2, 1, 1], [2, 2], [3, 1], [4]]

+0

'list(distribution)'仍然可以将分配分配解析为'all_distributions',这样'所有_分配“被改变为”分配“。 最好的方法是使用'deepcopy'。 '从拷贝导入deepcopy as dc' 然后将'list(distribution)'改为'dc(distribution)' –

+1

@GabrielS.Gusmão:'deepcopy'在这种情况下是过分的,因为''distribution'中的元素没有任何理由'应该递归地复制;使用'copy.copy'就足够了。当然,在这种情况下,'distribution'包含整数,所以它并不重要,但在选择'copy'或'deepcopy'之前,你应该总是考虑一下。 –

+0

你说得对。确实如此。但不应该使用'list'。改变它,所以我可以upvote答案。 –