我有一组可以包含多个“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')}
有没有更聪明的方法?或者我可以添加到代码中的一些优化?
1条答案
按热度按时间ruarlubt1#
使用
networkx
库,这是非常简单的,因为它有一个函数,可以完全满足您的要求:求图中的所有最大团。这里:
输出量:
当然,如果你的任务是自己实现Bron-Kerbosch算法,你就必须编写代码--但是在StackOverflow上提问就有点违背了目的,除非你的解决方案有特定的问题需要帮助?
如果你只是要求对你的代码进行审查,可以在Code Review Stack Exchange上询问,但也希望得到使用
networkx
的建议。