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

Question

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

给定一组 s 的 n 个元素，我们可以使用 Python 中的 itertools.combinations() 函数来查找所有唯一的 k 元素子集。我们将包含所有这些子集的集合称为S。请注意，每个这样的子集都有 k 个不同的元素。

问题有两步。首先，给定这些k-distinct-element子集，我想将它们(其中一些)组合起来(组合只是一些子集的超集):

1. 组合中任意两个子集之间的交集为空

2. 组合中所有子集之间的并集恰好给出原始集合s

其次，我想找到符合以下条件的作品:

1. 不共享任何子集

2. 它们的并集恰好给出了S，即所有k元素子集的集合

作为一个具体的例子，考虑原始集合s = {a, b, c, d}和k = 2，我们将有以下三个作品/超集:

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

显然，s的大小可能很大并且k >= 2，因此这里需要一种高效(尤其是速度)的算法。

附注我用两步来表述这个问题，但很可能高效的算法会从不同的角度来解决这个问题。

Answer 1

我实现了积分最大流构造，用于证明 Baranyai's theorem 。您最喜欢的教科书中涵盖完整超图因素的更多详细信息。

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)。当时我只能看到一半，因为我正在 Google 图书上查找，但现在有一个 PDF 版本。它是归纳证明的高级数学描述，它设置了最大流问题，展示了分数解，并断言整数解的存在，而无需详细说明如何获得它。我的 Python 实现使用 pipage 舍入来遵循证明的确切结构，但如果您只是想完成工作，我建议调用计算最大流量的 R 库(例如 igraph)。

让我快速举出一个如何设置最大流量的具体示例，因为在我弄清楚之前，抽象证明对我来说非常神秘。最小的重要示例是 n=6 且 k=3。这意味着我们有 (6-1) 选择 (3-1) = 10 个分区，每个分区有 2 组大小为 3 的分区。从所有元素为空的 10 x 2 x 3 数组开始，B&S 证明要求我们放置1(每行一个)，然后是 2，然后...，然后是 6。由于对称性的考虑，放置 1 很无聊，所以我就这样做而不做任何解释。 (您不需要在代码中对此进行特殊处理。)

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

从 2 开始，事情变得有趣。直观英语的关键不变量是我们希望每个经过审查的子集出现的次数与我们预期的一样多。在 6 个中选择 3 = 20 个大小为 3 的 {1, 2, ..., 6} 子集，其中数字 >2 用 进行审查，有 4 个选择 1 = 4 子集，看起来像 {1,2,} 和 4 选择 2 = 6(看起来像 {1,,})，4 选择 2 = 6(看起来像 {2,,})，4 选择 3 = 4 看起来像 {,,_}。我们想要做的是在每一行中放置一个 2 以获得此分布。很容易手动完成此操作:

{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,,}、3x {3,} >,}, 3 选择 3 = 1x {,,}。实际做出的选择!这就是最大流量发挥作用的地方。

让 ell 成为我们要放置的数字。我们构建的流网络有一个源、每行一个顶点、每个包含 ell 的删失子集的顶点以及一个接收器。从源到容量为 1 的每个行顶点都有一条弧。从每个删失子集 S 到容量 (n-1 - ell) 选择 (k - |S|) 的汇点都有一条弧。从每个行顶点到每个删失子集都有一条容量为 1 的弧，如果我们将 ell 放置在那里，该弧可能会出现在该行中。

在行上写上 a..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,_}

获取积分最大流量，这将在每一行中放置一个单元。放置位置看起来类似于

{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}

希望这有帮助!