python 如何还原N选2组合？

ht4b089n 于 12个月前发布在 Python

关注(0)|答案(1)|浏览(76)

我有一组可以包含多个“N选2”组合的结果的对：

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

我想把这些组合反过来，像这样：

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

来源：https://stackoverflow.com/questions/77153334/how-to-revert-n-choose-2-combinations

1条答案

按热度按时间

ruarlubt1#

使用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的建议。

赞(0）回复(0）举报 12个月前

我来回答

python 如何还原N选2组合？

1条答案

相关问题

热门标签

最新问答