我需要一种算法和/或Python代码,以生成将一个包含n个元素的集合分成零个或多个包含r个元素和一个余数的所有可能方式。例如,给定一个集合:
换句话说,从集合中提取0组两个项目的结果,加上从集合中提取1组两个项目的结果,再加上从集合中提取2组两个项目的结果……如果n更大,这个过程会继续下去。生成这些结果的顺序不重要,每个单独组内元素的顺序也不重要,结果中的组的顺序也不重要。(例如,((1,3),(2,4,5))等同于((3,1),(4,5,2))和((2,5,4),(1,3))等等)。我想要的是每个不同的结果至少产生一次,并且最好只产生一次,以尽可能高效的方式实现。
暴力方法是生成所有可能的长度为
[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
比较大时,其中有相当数量的重复项。因此,我希望有一个算法可以避免这些重复项。