找到的k不同元件子集的独特的组合物为一组n个元素的(Find unique compositions

这是一个算法问题。如果我错过了在Python任何现有的功能，可以帮助，请给留言。

给定一组s的n元素，我们可以使用itertools.combinations()函数在Python中找到的所有独特的k元素子集 。让我们把所有包含这些子集的集S 。请注意，每个这样的子集具有k不同的元素。

问题是两步骤。首先，鉴于这些K-不同元素的子集，我想组成（某些）它们使得（a组合物仅仅是一些子集的超集）：

的组合物内的任何两个子集之间的交集为空
在组合物中所有的子集之间的联盟提供了准确的原始组s

其次，我想找到的成分：

不共享任何集
他们的结合使完全S ，也就是集中所有的k -元素的子集

如这里具体的例子，考虑原始集合s = {a, b, c, d}和k = 2 ，我们然后将具有以下三种组合物/超集：

{{a, b}, {c, d}}, {{a, c}, {b, d}}, {{a, d}, {b, c}}

显然，尺寸s可能很大，并且k >= 2 ，因此这里需要有效的（特别是速度）算法。

PS我短语在2个步骤的问题，但它可能是，一个有效的算法从一个不同的角度攻击问题。

我实现了这是我们用来证明积分最大流量建设鲍劳尼奥伊定理。在你最喜欢的教科书更多细节覆盖了完整的超图的因素。

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