找K-不同的元素子集的独特组合为一组n个元素 [英] Find unique compositions of k-distinct-element subsets for a set of n elements
问题描述
这是一个算法问题。如果我错过了在Python中的任何现有功能的帮助，请给留言。
This is an algorithmic problem. If I miss any existing function in Python that helps, please give a shout.
鉴于 N 元素的集合取值，我们可以使用 itertools.combinations（在Python）函数找到所有的独特的 K元素的子集的。让我们把包含所有这些子集取值设定。请注意，每个这样的子集具有 K 不同的元素。
Given a set s of n elements, we can use itertools.combinations() function in Python to find all the unique k-element subsets. Let's call the set containing all these subsets S. Notice that each such subset has k distinct elements.
问题是两步骤。首先，考虑到这些的 K-不同的元素的子集，我想组成（部分）他们这样的（组成只是部分子集的一个超集）：
The problem is 2-step. First, given these k-distinct-element subsets, I want to compose (some of) them such that (a composition is simply a superset of some subsets):
-
组合物中的任何两个子集之间的交集为空
The intersection between any two subsets within a composition is empty
在一个组合物中所有的子集之间的联盟提供了完全原载取值
The union between all the subsets in a composition gives exactly the original set s
二，我想找到的组合物：
Second, I want to find the compositions that:
-
不共享任何一个子集
Do not share any subset
他们的结合使完全取值，即集所有的 K k-元子集
Their union gives exactly the S, i.e. the set of all the k-element subsets
由于这里一个具体的例子，考虑原来设置 S = {A，B，C，D} 和 K = 2 ，我们届时将有以下三种成分/超集：
As a concrete example here, consider the original set s = {a, b, c, d} and k = 2, we then will have the following three compositions/supersets:
{{A，B}，{C，D}}，{{A，C}，{B，D}}，{{A，D}，{B，C}}
显然，取值规模可能很大， K＆GT; = 2 ，所以一个有效的（特别是速度）算法，这里需要的。
Obviously, the size of s can be large and k >= 2, so an efficient (especially the speed) algorithm is needed here.
P.S。我短语在2个步骤的问题，但它可能是，一个有效的算法从一个不同的角度攻击问题
P.S. I phrase the problem in 2 steps, but it may well be that an efficient algorithm attacks the problem from a different angle.
推荐答案
我实现了这是我们用来证明的 Baranyai定理。更多细节在你最喜欢的教材涵盖了完整的超图的因素。
I implemented the integral maximum flow construction that's used to prove Baranyai's theorem. More details in your favorite textbook covering factors of a complete hypergraph.
from collections import defaultdict
from fractions import Fraction
from math import factorial
from operator import itemgetter
def binomial(n, k):
return factorial(n) // (factorial(k) * factorial(n - k))
def find_path(graph, s, t):
stack = [s]
predecessor = {s: t}
while stack:
v = stack.pop()
for u in graph[v]:
if u not in predecessor:
stack.append(u)
predecessor[u] = v
assert t in predecessor
path = [t]
while path[-1] != s:
path.append(predecessor[path[-1]])
path.reverse()
return path
def round_flow(flow):
while True:
capacities = []
for (u, v), x in flow.items():
z = x - x.numerator // x.denominator
if z:
capacities.append(((v, u), z))
capacities.append(((u, v), 1 - z))
if not capacities:
break
(t, s), delta = min(capacities, key=itemgetter(1))
graph = defaultdict(list)
for (v, u), z in capacities:
if (v, u) not in [(s, t), (t, s)]:
graph[v].append(u)
path = find_path(graph, s, t)
for i, v in enumerate(path):
u = path[i - 1]
if (u, v) in flow:
flow[(u, v)] += delta
else:
flow[(v, u)] -= delta
def baranyai(n, k):
m, r = divmod(n, k)
assert not r
M = binomial(n - 1, k - 1)
partition = [[()] * m for i in range(M)]
for l in range(n):
flow = defaultdict(Fraction)
for i, A_i in enumerate(partition):
for S in A_i:
flow[(i, S)] += Fraction(k - len(S), n - l)
round_flow(flow)
next_partition = []
for i, A_i in enumerate(partition):
next_A_i = []
for S in A_i:
if flow[(i, S)]:
next_A_i.append(S + (l,))
flow[(i, S)] -= 1
else:
next_A_i.append(S)
next_partition.append(next_A_i)
partition = next_partition
assert len(partition) == M
classes = set()
for A in partition:
assert len(A) == m
assert all(len(S) == k for S in A)
assert len({x for S in A for x in S}) == n
classes.update(map(frozenset, A))
assert len(classes) == binomial(n, k)
return partition
if __name__ == '__main__':
print(baranyai(9, 3))
print(baranyai(20, 2))
这篇关于找K-不同的元素子集的独特组合为一组n个元素的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
