时间戳

首页 > 解决方案 > 有没有更好的方法来遍历集合 (A, B, C) 选择 (a, b, c)

python - 有没有更好的方法来遍历集合 (A, B, C) 选择 (a, b, c)

问题描述

我有 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}

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

标签： pythonalgorithmset

解决方案

从每个集合中选择不同数量的项目的问题可以转换为通过重复集合所需的次数来从新集合中的每个集合中选择一个项目，即 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)，其边连接 N(A_i) 和 N(x_j) 如果 x_j 在 A_i 中，则查找 sdr 的问题与问题相同找到覆盖每个 N(A_i) 的该图的匹配。这样的匹配是最大匹配，所以如果至少存在一个匹配， Hopcroft Karp 算法就会找到它。因此，要查看一组集合是否在其图上运行 hopcroft karp 的 sdr，然后检查每个 N(A_i) 的匹配覆盖

我们如何检查输出集是否有效？（例如示例中的{1,2,3,4,9,13,15}）有效输出集的元素与输入集A_i至少一一对应，即设输出集为W = { y_0 , y_1, ... , y_n } 那么如果我们构造一个新的集合集合 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 方法看起来更快

推荐阅读