一個列表的所有k路分區遞歸算法

Question

我寫一個函數，應該輸出的所有列表A. 此問題的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?（第一回答）

我不明白的是這個特定函數的行爲。

Answer 1

好，所以問題是行tt = list(ss)這只是列表的淺拷貝。使用tt = copy.deepcopy(ss)解決了這個問題。

Answer 2

一個問題可能是[ [] ] * 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跳閘 - 但它應該有所幫助。