找到n个元素集合的k-不同元素子集的唯一组合

Question

这是一个算法问题。如果我错过了Python中任何有帮助的现有函数，请大喊一声。

给定一组n元素的s，我们可以在Python中使用itertools.combinations（）函数来找到所有唯一的k元素子集。让我们调用包含所有这些子集的集合S。请注意，每个这样的子集都有k不同的元素。

问题是两步走。首先，给定这些k-不同元素子集，我想组合（其中的一些），这样（组合只是一些子集的超集）：

>

构图中任意两个子集之间的交集为空

构图中所有子集的并集给出的正是原始集合s

第二，我想找到以下组成部分：

>

不共享任何子集

它们的联合给出了S，即所有k-元素子集的集合

作为一个具体的例子，考虑原始集合<代码> s= {a，b，c，d} < /代码>和<代码> k＝2 < /代码>，我们将有以下三个构图/超集：

{a，b}，{c，d}，{a，c}，{b，d}，{a，d}，{b，c}

显然，s的大小可以很大，k

P.S.I.将问题分为两步，但一个有效的算法很可能从不同的角度来解决问题。




Answer 1

我实现了积分最大流构造，用来证明Baranyai定理。在你最喜欢的教科书中有更多关于完整超图的细节。

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

让我把我写的一封关于这个答案的电子邮件扔到这里，因为它可能对其他人有用。

不幸的是，没有什么比这更适合作为音译的来源了。

我使用的结构是由于Brouwer和Schrijver（1979年）。当时我只能看到其中的一半，因为我在谷歌图书上搜索，但现在有一个PDF漂浮在周围。这是一个归纳证明的高级数学描述，它建立了一个最大流问题，展示了一个分数解，并断言了一个整数解的存在，而没有详细说明如何得到它。我的Python实现使用pipage舍入来遵循证明的确切结构，但如果您只是想完成工作，我建议调用计算最大流的R库（例如igraph）。

让我用一个具体的例子来说明如何设置最大流，因为在我弄明白之前，html" target="_blank">抽象证明对我来说是非常神秘的。最小的非平凡例子是n=6和k=3。这意味着我们有（6-1）选择（3-1）=10个分区，每个分区有2组大小为3的分区。从一个所有元素都为空的10×2×3数组开始，B

{1,_,_}, {_,_,_}
{1,_,_}, {_,_,_}
{1,_,_}, {_,_,_}
{1,_,_}, {_,_,_}
{1,_,_}, {_,_,_}
{1,_,_}, {_,_,_}
{1,_,_}, {_,_,_}
{1,_,_}, {_,_,_}
{1,_,_}, {_,_,_}
{1,_,_}, {_,_,_}

从2s开始，事情变得有趣起来。直观英语中的关键不变量是，我们希望每个被删除的子集出现的次数与我们预期的一样多。在6个子集中，选择3=20个带数字的{1, 2, ..., 6}大小-3子集

{1,2,_}, {_,_,_}
{1,2,_}, {_,_,_}
{1,2,_}, {_,_,_}
{1,2,_}, {_,_,_}
{1,_,_}, {2,_,_}
{1,_,_}, {2,_,_}
{1,_,_}, {2,_,_}
{1,_,_}, {2,_,_}
{1,_,_}, {2,_,_}
{1,_,_}, {2,_,_}

当我们到3时，我们有3个选择0=1x{1,2,3}，3个选择1=3x{1,2，}，3x{1,3，}，3x{2,3，}，3个选择2=3x{1，，，}，3x{2，，，，，}，3个选择3=1x{，，，}。真正的选择！这就是最大流量的作用。

让我们把电话号码设为ell。我们构造的流网络有一个源，每行有一个顶点，每个包含ell的删失子集有一个顶点，还有一个汇。从源到容量1的每行顶点都有一条弧。从每个截尾子集S到容量汇（n-1-ell）choose（k-| S |）有一条弧。从每一行顶点到每一个删失子集有一个容量为1的弧，如果我们把ell放在那里，它可能会出现在那一行中。

一行一行的字母。。j、 中间的弧线看起来像

a-->{1,2,3}
a-->{3,_,_}
b-->{1,2,3}
b-->{3,_,_}
c-->{1,2,3}
c-->{3,_,_}
d-->{1,2,3}
d-->{3,_,_}
e-->{1,3,_}
e-->{2,3,_}
...
j-->{1,3,_}
j-->{2,3,_}

得到一个积分最大流量，这将在每一行中恰好放置一个ell。位置看起来像

{1,2,3}, {_,_,_}
{1,2,_}, {3,_,_}
{1,2,_}, {3,_,_}
{1,2,_}, {3,_,_}
{1,3,_}, {2,_,_}
{1,3,_}, {2,_,_}
{1,3,_}, {2,_,_}
{1,_,_}, {2,3,_}
{1,_,_}, {2,3,_}
{1,_,_}, {2,3,_}

一直持续到我们

{1,2,3}, {4,5,6}
{1,2,4}, {3,5,6}
{1,2,5}, {3,4,6}
{1,2,6}, {3,4,5}
{1,3,4}, {2,5,6}
{1,3,5}, {2,4,6}
{1,3,6}, {2,4,5}
{1,4,5}, {2,3,6}
{1,4,6}, {2,3,5}
{1,5,6}, {2,3,4}

希望这有帮助！