生成所有固定长度组合的方法

Question

生成所有固定长度组合的方法

5

我需要一种算法和/或Python代码，以生成将一个包含n个元素的集合分成零个或多个包含r个元素和一个余数的所有可能方式。例如，给定一个集合：

[1,2,3,4,5]

使用n = 5和r = 2，我想得到

((1,2,3,4,5),)
((1,2),(3,4,5))
((1,3),(2,4,5))
...
((1,2),(3,4),(5,))
((1,2),(3,5),(4,))
...

换句话说，从集合中提取0组两个项目的结果，加上从集合中提取1组两个项目的结果，再加上从集合中提取2组两个项目的结果……如果n更大，这个过程会继续下去。生成这些结果的顺序不重要，每个单独组内元素的顺序也不重要，结果中的组的顺序也不重要。（例如，((1,3),(2,4,5))等同于((3,1),(4,5,2))和((2,5,4),(1,3))等等）。我想要的是每个不同的结果至少产生一次，并且最好只产生一次，以尽可能高效的方式实现。

暴力方法是生成所有可能的长度为r的组合，然后创建由这些组合中任意数量的所有可能组成的组（powerset），迭代它们，并只处理组中组合没有共同元素的那些。即使是很少的元素也需要太长时间（需要迭代2^(n!/r!(n-r)!)个组，因此复杂度是双指数级别）。基于this question中给出的代码，这本质上是r = 2和n偶数的特例，我想到了以下方法：

def distinct_combination_groups(iterable, r):
    tpl = tuple(iterable)
    yield (tpl,)
    if len(tpl) > r:
        for c in combinations(tpl, r):
            for g in distinct_combination_groups(set(tpl) - set(c), r):
                yield ((c,) + g)

这个算法似乎生成了所有可能的结果，但是包含一些重复项，当n比较大时，其中有相当数量的重复项。因此，我希望有一个算法可以避免这些重复项。

- David Z

在这里http://math.stackexchange.com/questions/222780/enumeration-of-partitions中，您可以找到Knuth的“计算机程序设计艺术”第4卷的3b册的链接。 - Teudimundo

1

@Teudimundo：你的链接是关于找到n个元素分成恰好k组的问题，每组可以有任意大小。但是这里的OP想要将n个元素分成任意数量的大小恰好为r的组（可能还有一些余数）。 - Gareth Rees

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Gareth Rees · Accepted Answer

这个怎么样？

from itertools import combinations

def partitions(s, r):
    """
    Generate partitions of the iterable `s` into subsets of size `r`.

    >>> list(partitions(set(range(4)), 2))
    [((0, 1), (2, 3)), ((0, 2), (1, 3)), ((0, 3), (1, 2))]
    """
    s = set(s)
    assert(len(s) % r == 0)
    if len(s) == 0:
        yield ()
        return
    first = next(iter(s))
    rest = s.difference((first,))
    for c in combinations(rest, r - 1):
        first_subset = (first,) + c
        for p in partitions(rest.difference(c), r):
            yield (first_subset,) + p

def partitions_with_remainder(s, r):
    """
    Generate partitions of the iterable `s` into subsets of size
    `r` plus a remainder.

    >>> list(partitions_with_remainder(range(4), 2))
    [((0, 1, 2, 3),), ((0, 1), (2, 3)), ((0, 2), (1, 3)), ((0, 3), (1, 2))]
    >>> list(partitions_with_remainder(range(3), 2))
    [((0, 1, 2),), ((1, 2), (0,)), ((0, 2), (1,)), ((0, 1), (2,))]
    """
    s = set(s)
    for n in xrange(len(s), -1, -r): # n is size of remainder.
        if n == 0:
            for p in partitions(s, r):
                yield p
        elif n != r:
            for remainder in combinations(s, n):
                for p in partitions(s.difference(remainder), r):
                    yield p + (remainder,)

原帖中的示例：

>>> pprint(list(partitions_with_remainder(range(1, 6), 2)))
[((1, 2, 3, 4, 5),),
 ((4, 5), (1, 2, 3)),
 ((3, 5), (1, 2, 4)),
 ((3, 4), (1, 2, 5)),
 ((2, 5), (1, 3, 4)),
 ((2, 4), (1, 3, 5)),
 ((2, 3), (1, 4, 5)),
 ((1, 5), (2, 3, 4)),
 ((1, 4), (2, 3, 5)),
 ((1, 3), (2, 4, 5)),
 ((1, 2), (3, 4, 5)),
 ((2, 3), (4, 5), (1,)),
 ((2, 4), (3, 5), (1,)),
 ((2, 5), (3, 4), (1,)),
 ((1, 3), (4, 5), (2,)),
 ((1, 4), (3, 5), (2,)),
 ((1, 5), (3, 4), (2,)),
 ((1, 2), (4, 5), (3,)),
 ((1, 4), (2, 5), (3,)),
 ((1, 5), (2, 4), (3,)),
 ((1, 2), (3, 5), (4,)),
 ((1, 3), (2, 5), (4,)),
 ((1, 5), (2, 3), (4,)),
 ((1, 2), (3, 4), (5,)),
 ((1, 3), (2, 4), (5,)),
 ((1, 4), (2, 3), (5,))]