python - 有没有更好的方法来迭代集合(A，B，C)选择(a，b，c)

Question

我有 1 到 9 个可能重叠的集合，我需要从每个集合中选择 1 到 3 个元素，这样最后我就没有重复项。

对于每个有效的排列，我需要进行一些处理。

理想情况下，我想要可扩展的解决方案(这样我就可以学习最佳实践!)

一些不好的想法:

1. 可变数量的嵌套/递归循环。优点:不会在无效选项上浪费时间。缺点:在重复的集合上浪费时间，而且丑陋。

2. 迭代地从所有集合的并集中选择所需的总数，然后进行验证。优点:更少嵌套，没有重复集。缺点:检查每个无效选项。未知:根据我在 math.stackexchange 上提出的问题，验证可能是瞬时的或需要处理。

示例:

A={1,3,5,7,9,11,13,15} choose 3  
B={4,7,8,9,10,12} choose 2  
C={1,2,5,6,7,14} choose 2

可能的结果 {1,2,3,4,9,13,15}

是否有比我上面列出的方法更好的方法来访问每个有效结果？

Answer 1

从每组中选择不同数量的项目的问题可以转换 通过重复以下操作从新的集合集合中的每个集合中选择一个项目 设置所需的次数，即 A 选择 3 ， B 选择 2 ， C 选择 2 变为 从 A、A、A、B、B、C、C 中各选择 1 个。 现在的问题是寻找不同代表制度(SDR)。

可以通过以下方式查找一组集合是否至少有一个 sdr。 设集合的集合为 S = { A_0 , A_1 , A_3 , ... , A_n } X 是所有 A_i 的并集，并将其元素称为 x_0 、 x_1 、 x_2 、... 考虑(二分)图，其中每个 A_i 的节点称为 N(A_i)，每个 x_i 的节点称为 N(x_i)，如果 x_j 在 A_i 中，则边将 N(A_i) 与 N(x_j) 连接起来 寻找 sdr 的问题与寻找覆盖每个 N(A_i) 的图的匹配问题相同。这样的匹配是最大匹配，因此如果至少存在一个 Hopcroft Karp algorithm会找到它。因此，要查看集合的集合是否具有 sdr，请在其图上运行 hopcroft karp，然后检查匹配覆盖每个 N(A_i)

我们如何检查输出集是否有效？ (例如示例中的 {1,2,3,4,9,13,15}) 有效输出集的元素与输入集 A_i 至少具有一一对应关系 即，让输出集为 W = { y_0 , y_1, ... , y_n } 那么至少有一种方法可以为每个 y_j 选择不同的 A_i ，使得 y_j 在 A_i 中 如果我们构造一个新的集合 SN = { B_0 , B_1, B_3, ... , B_N } 其中 B_i 是包含 y_i 的集合 A_j 的集合 找到这个对应关系只是找到 SN 的 SDR。因此，要检查输出集是否有效，请检查是否存在此新集合集合的 sdr。 另外，如果我们对 W 的一个子集进行这种构造，那么如果 W 有一个 sdr，那么就会有一个 sdr

使用模块 networkx 来实现 hopcroft karp，以下检查集合的集合是否具有 sdr

import networkx as nx

def hasSDR(s):
    x=set.union(*s)
    setnames = ["set"+str(i+1) for i in range(len(s)) ]
    B = nx.Graph()
    B.add_nodes_from( setnames , bipartite=0)
    B.add_nodes_from( x , bipartite=1)
    B.add_edges_from( [( setnames[i] , j ) for i in range(len(s)) for j in s[i] ] )
    hk = nx.bipartite.hopcroft_karp_matching(B,top_nodes=setnames)
    return all( i in hk for i in setnames )

然后我们可以通过以下方式查找输出集是否有效(假设其大小正确)

def possibleSDRSet( s , w ):
    sn = [ { j for j in range(len(s)) if i in s[j] } for i in w ]
    return hasSDR( sn )

如果给定此函数的 w 的大小小于集合中的集合数，则仅当 w 是无有效输出集的子集时才会返回 false

循环遍历 X 的长度为 n 的所有子集，然后测试它们是否是我们可以做的有效输出集(使用生成器)(这是问题中的想法 2)

def allsets( s , req = set() ):
    if len(req) == len(s):
        if possibleSDRSet( s , req ): yield req
        return
    x = set.union(*s) - req
    if len(x) == 0: return
    xr = x.pop()
    sr = [i - {xr} for i in s]
    for i in allsets( sr , req ): yield i
    for i in allsets( s , req | {xr} ): yield i

这将集合和所需元素集作为参数，然后选择不在所需集合中的元素， 然后，它将搜索拆分为不包含该元素的集合和包含该元素的集合；第一步是创建一个新的集合集合，并从集合中的所有集合中删除该元素 第二个是将元素添加到所需的集合中

然而，其中许多分支可能不需要考虑，当我们从集合中的所有集合中删除一个元素时，可能不再有 sdr，因此我们可以检查 如果仍然存在具有 hasSDR 的 sdr，并且只有在存在时才在该分支中继续。 当我们将一个元素添加到所需列表时 possibleSDRSet 可能能够排除该分支中存在任何 SDR，因此我们也可以检查这一点，给出

def _findSDRSetsRec( s , req ):
    if len(req) == len(s):
        yield req
        return
    x = set.union(*s) - req
    xr = x.pop()
    sr = [ i - {xr} for i in s ]
    if hasSDR( sr ):
        for i in _findSDRSetsRec( sr , req ): yield i
    reqp = req | {xr}
    if possibleSDRSet( s , reqp ):
        for i in _findSDRSetsRec( s , reqp ): yield i

def findSDRSets(s):
    if not hasSDR(s): return
    for i in _findSDRSetsRec( s , set() ): yield i

这些函数中的第一个假设 s 和 req 已通过两个测试进行检查，因此需要一个包装器来检查是否存在 sdr。 做例子:

s = ({1,3,5,7,9,11,13,15},)*3 +({4,7,8,9,10,12},)*2 + ({1,2,5,6,7,14},)*2
for i in findSDRSets(s): print(i)

如果只有少量有效输出集，则使用此方法应该比您列出的方法更快，但是对于给定的示例，allsets 方法看起来更快