主页 / coding / 问题 / 77153334
Accepted
Fravadona
Asked: 2023-09-22 04:05:39 +0800 CST

如何撤销2阶组合？

  • 772

我有一组对：

inputs = {
    ('id1', 'id2'), ('id1', 'id3'), ('id1', 'id4'),
    ('id2', 'id3'), ('id2', 'id4'),
    ('id3', 'id4'), ('id3', 'id5'),
    ('id4', 'id5'),
    ('id5', 'id6'),
}

我想反转 2 阶的组合，如下所示：

recombinations = [
    ('id1', 'id2', 'id3', 'id4'),
    ('id3', 'id4', 'id5'),
    ('id5', 'id6'),
]

我设法使用暴力来做到这一点：

ids = list(sorted( {i for i in itertools.chain(*inputs)} ))

excludes = set()
recombinations = {tuple(i) for i in map(sorted, inputs)}

for i in range(3, len(ids)+1):
    for subset in itertools.combinations(ids, i):
        for j in range(i-1, len(subset)):
            combs = set(itertools.combinations(subset, j))
            if all(tup in recombinations for tup in combs):
                recombinations.add(subset)
                excludes = excludes.union(combs)

for tup in excludes:
    recombinations.remove(tup)

print(recombinations)

{('id1', 'id2', 'id3', 'id4'), ('id3', 'id4', 'id5'), ('id5', 'id6')}

我的问题是：是否有更智能的方法来做到这一点，或者我可以在代码中实现一些优化？

python

1 个回答

  1. Best Answer

    使用该networkx库，这非常简单，因为它有一个函数可以完全满足您的要求：查找图中的所有最大派系。

    这里：

    import networkx as nx

G = nx.Graph()

pairs_of_connected_nodes = [
    ('id1', 'id2'), ('id1', 'id3'), ('id1', 'id4'),
    ('id2', 'id3'), ('id2', 'id4'),
    ('id3', 'id4'), ('id3', 'id5'),
    ('id4', 'id5'),
    ('id5', 'id6')
]

G.add_edges_from(pairs_of_connected_nodes)

maximal_cliques = list(nx.find_cliques(G))

for clique in maximal_cliques:
    print(clique)

    输出：

    ['id3', 'id4', 'id2', 'id1']
['id3', 'id4', 'id5']
['id6', 'id5']

    当然，如果你的任务是自己实现 Bron-Kerbosch 算法，你就必须对其进行编码 - 但然后在 StackOverflow 上询问有点达不到目的，除非你的解决方案有特定问题需要帮助？

    如果您只是要求对您的代码进行审查，请在 Code Review Stack Exchange 上询问，但也会被告知使用networkx。

    • 4

相关问题