python - 如何找到列表S的所有分区为k个子集(可以为空)？

Question

我有一个唯一元素列表，比方说 [1,2]，我想将其拆分为 k=2 个子列表。现在我想要所有可能的子列表:

[ [ [1,2],[] ], [ [1],[2] ], [ [2],[1] ], [ [],[1,2] ] ]

我想分割成 1<=k<=n 个子列表，所以对于 k=1 它将是:

[ [1, 2] ]

如何使用 Python 3 做到这一点？

更新:我的目标是获取 N 个唯一数字列表的所有可能分区，其中每个分区将有 k 个子列表。我想展示比我上面展示的更好的例子，我希望我不会错过任何东西。因此，对于列表 [1, 2, 3] 和 k=2 我想要下一个列表:

[
[ [1,2,3], [] ],
[ [2,3], [1] ],
[ [1,3], [2] ],
[ [1,2], [3] ],
[ [1], [2,3] ],
[ [2], [1,3] ],
[ [3], [2,3] ],
[ [], [1,2,3] ]
] 

更新2:到目前为止，我结合了两个建议，并进行了少量修改，得到了下一个代码:

def sorted_k_partitions(seq, k):
    """Returns a list of all unique k-partitions of `seq`.

    Each partition is a list of parts, and each part is a tuple.

    The parts in each individual partition will be sorted in shortlex
    order (i.e., by length first, then lexicographically).

    The overall list of partitions will then be sorted by the length
    of their first part, the length of their second part, ...,
    the length of their last part, and then lexicographically.
    """
    n = len(seq)
    groups = []  # a list of lists, currently empty

    def generate_partitions(i):
        if i >= n:
            yield list(map(tuple, groups))
        else:
            if n - i > k - len(groups):
                for group in groups:
                    group.append(seq[i])
                    yield from generate_partitions(i + 1)
                    group.pop()

            if len(groups) < k:
                groups.append([seq[i]])
                yield from generate_partitions(i + 1)
                groups.pop()

    result = generate_partitions(0)

    # Sort the parts in each partition in shortlex order
    result = [sorted(ps, key = lambda p: (len(p), p)) for ps in result]
    # Sort partitions by the length of each part, then lexicographically.
    result = sorted(result, key = lambda ps: (*map(len, ps), ps))

    return result

通过这个函数我可以做下一步:

import itertools as it
k=2
S = [1, 2, 3]
for i in (range(k)):
    for groups in sorted_k_partitions(S, k-i):
        for perm in it.permutations(groups+[tuple() for j in range(i)]):
            print(perm)

输出为:

((1,), (2, 3))
((2, 3), (1,))
((2,), (1, 3))
((1, 3), (2,))
((3,), (1, 2))
((1, 2), (3,))
((1, 2, 3), ())
((), (1, 2, 3))

我还不确定，这段代码是否给了我正确的解决方案，也许还有其他方法？

Answer 1

这是一个替代解决方案:

def partition_k(l, k):
    n = len(l)
    if k > n:
        raise ValueError("k = {0} should be no more than n = {1}".format(k, n))

    if n == 0:
        yield []
        return

    pos = [0] * n
    while True:
        # generate output for the value
        out = [[] for _ in range(k)]
        for i in range(n):
            out[pos[i]].append(l[i])
        yield out

        #increment the value
        pos[0] += 1
        for i in range(n):
            # should we carry from this digit to the next one?
            if pos[i] == k:
                # overflow of the whole value?
                if i == n - 1:
                    return
                pos[i] = 0
                pos[i + 1] += 1
            else:
                break

令n 为列表的长度，k 为分区数。该代码背后的想法是，输出的每一行都可以表示为基k 系统中的n 位数字。每个“数字”表示相应位置的值位于哪个桶中。例如行

[[2,3], [1], [4]]

可以编码为[1,0,0,2]，这意味着

• 1 转到存储桶#1
• 2 转到存储桶#0
• 3 转到存储桶 #0
• 4 转到存储桶#2

显然，每个这样的n位基数k数字代表列表的有效分区，并且每个分区都由某个数字表示。因此，要生成所有分区，我们只需迭代所有这些数字并生成相应的分区。如果您使用数字列表来表示数字(在代码中为 pos)，则更容易做到。