我希望找到一种算法,可以给定一个集合A,找到所有满足以下条件的子集组:
我得到了以下输出,它们都是由两个子集组成的组。
x ∪ y ∪ .... z = A,其中x,y,... z ∈ Group
并且
∀ x,y ∈ Group: x ⊆ A,y ⊆ A,x ∩ y = ∅ = {}
并且
∀ x ∈ Group: x != ∅
注意:我希望定义清楚,我不擅长数学符号。
我制定了以下方法仅搜索两个子集的组:
from itertools import product, combinations
def my_combos(A):
subsets = []
for i in xrange(1, len(A)):
subsets.append(list(combinations(A,i)))
combos = []
for i in xrange(1, 1+len(subsets)/2):
combos.extend(list(product(subsets[i-1], subsets[-i])))
if not len(A) % 2:
combos.extend(list(combinations(subsets[len(A)/2-1], 2)))
return [combo for combo in combos if not set(combo[0]) & set(combo[1])]
my_combos({1,2,3,4})
我得到了以下输出,它们都是由两个子集组成的组。
[
((1,), (2, 3, 4)),
((2,), (1, 3, 4)),
((3,), (1, 2, 4)),
((4,), (1, 2, 3)),
((1, 2), (3, 4)),
((1, 3), (2, 4)),
((1, 4), (2, 3))
]
......但是,由一个、三个、四个子集组成的群组....
问题:
我该如何找到一个通解?
例如以下预期输出:
my_combos({1,2,3,4})
[
((1,2,3,4)),
((1,2,3),(4,)),
((1,2,4),(3,)),
((1,3,4),(2,)),
((2,3,4),(1,)),
((1,2),(3,4)),
((1,3),(2,4)),
((1,4),(2,3)),
((1,2),(3,),(4,)),
((1,3),(2,),(4,)),
((1,4),(2,),(3,)),
((1,),(2,),(3,4)),
((1,),(3,),(2,4)),
((1,),(4,),(2,3)),
((1,),(4,),(2,),(3,))
]