0

我正在编写一个函数，它应该输出列表 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) ]

输出

断言错误：

[[]，[]]

[[0], [0]]

我不明白输出。它应该[[0], []]代替[[0], [0]]. 我错过了什么？

注意：我知道如何编写一个不同的函数，否则append它会输出正确的结果。将所有分区迭代成k组？（第一个答案）

我不明白的是这个特定功能的行为。

4

2 回答 2

1

一个问题可能是[ [] ] * 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-14T03:56:55.087 回答
0

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

于 2013-10-14T12:39:42.103 回答