一个列表的所有k路分区递归算法

我写一个函数，应该输出的所有列表A. 此问题的K-方式划分显然是递归的，并且实施应该是直接的：一个列表的所有k路分区递归算法

def gen_partition_k_group(A, k): 
    # 
    if len(A) == 0 : 
     # EDITED FOLLOWING SUGGESTION 
     yield [ [] for _ in xrange(k) ] 
    # 
    else : 
     # all k-partitions of the list of size N-1 
     for ss in gen_partition_k_group(A[:-1], k) : 
      assert(sum(len(gg) for gg in ss) == len(A) -1) 
      for ii in xrange(k) : 
       tt = list(ss) 
       print tt 
       tt[ ii ].append(A[ -1 ]) 
       print tt 
       assert(sum(len(gg) for gg in tt) == len(A)) 
       yield tt 

A = range(3) 
k = 2 
[ xx for xx in gen_partition_k_group(A, k) ]

输出

AssertionError:

[[], []]

[[0], [0]]

我不明白的输出。它应该是[[0], []]而不是[[0], [0]]。我错过了什么？

注：我知道如何编写一个不同的功能，而不需要append，它输出正确的结果。 Iterator over all partitions into k groups?（第一回答）

我不明白的是这个特定函数的行为。

来源

2013-10-14 usual me

你知道'[[]] * k'为非零'k'会创建该相同列表的'k'个副本，对吗？ – kojiro

好，所以问题是行tt = list(ss)这只是列表的浅拷贝。使用tt = copy.deepcopy(ss)解决了这个问题。

来源

2013-10-14 12:39:42

一个问题可能是[ [] ] * k不符合您的想法。这不会使空列表k，它使一个新的空列表和k引用它。例如：

>>> [[]]*3 
[[], [], []] 
>>> a = [[]]*3 
>>> a 
[[], [], []] 
>>> a[0].append(1) 
>>> a 
[[1], [1], [1]] 
>>> id(a[0]), id(a[1]), id(a[2]) 
(25245744, 25245744, 25245744) 
>>> a[0] is a[1] 
True 
>>> a[0] is a[2] 
True

要进行多新的列表，你可以不喜欢

>>> a = [[] for _ in xrange(3)] 
>>> a 
[[], [], []] 
>>> id(a[0]), id(a[1]), id(a[2]) 
(41563560, 41564064, 41563056)

我不认为这本身将解决您的计划 - 我仍然得到一个assert跳闸 - 但它应该有所帮助。

来源

2013-10-14 03:56:55 DSM

谢谢。你有没有关于这个'[[]] * k'表示法的参考？我找不到任何东西。 –

一个列表的所有k路分区递归算法

回答

相关问题