如何找到列表S的所有分区为k个子集(可以为空)? [英] How to find all partitions of a list S into k subsets (can be empty)?

问题描述

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

I have a list of unique elements, let's say [1,2], and I want to split it onto k=2 sublists. Now I want to have all possible sublists:

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

我想拆分为1< = k< = n子列表，因此对于k = 1它将是:

And I want to split onto 1<=k<=n sublists, so for k=1 it will be:

[ [1, 2] ]

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

How can I do that with Python 3?

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

UPDATE: my goal is to get all possible partitions of list of N unique numbers, where each partition will have k sublists. I would like to show better example than I have shown upper, I hope I will not miss something. So for list [1, 2, 3] and for k=2 I want to have next list:

[
[ [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:到目前为止，我已经结合了两个建议，几乎没有修改就得到了下一个代码:

UPDATE 2: so far I have combined two suggestions and little modification got next code:

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

使用此功能，我可以下一步:

With this function I can do next:

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))

我不确定，这段代码是否能为我提供正确的解决方案，也许还有其他方法?

I'm not sure yet, that this code gives me right solution, maybe there is other way?

推荐答案

以下是替代解决方案:

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是分区的数量.该代码背后的思想是，在base- k系统中，输出的每一行都可以表示为许多n位.每个数字"表示在相应位置哪个值所在的存储桶.例如line

Let n be the length of the list and k is the number of partitions. The idea behind this code is that each line of the output can be represented as a number of n digits in base-k system. Each "digit" shows in which bucket goes the value at corresponding position. For example line

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

可以编码为[1,0,0,2]，表示

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

• 1 goes to the bucket #1
• 2 goes to the bucket #0
• 3 goes to the bucket #0
• 4 goes to the bucket #2

很显然，每个这样的n位以base- k开头的数字都代表列表的有效分区，并且每个分区都由某个数字表示.因此，要生成所有分区，我们只需要遍历所有此类数字并生成相应的分区即可.如果使用数字列表来表示数字(在代码中为pos)，则更容易做到.

Obviously every such n-digits base-k number represents a valid partition of the list and each partition is represented by some number. So to generate all partitions we need just iterate through all such numbers and generate corresponding partitions. It is easier to do if you use a list of digits to represent a number (in the code this is pos).

这篇关于如何找到列表S的所有分区为k个子集(可以为空)?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！