如何恢复N选2组合？

Question

如何恢复N选2组合？

3

我有一组可以包含多个“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')}

有没有更聪明的方法来做这件事？或者有一些优化的代码可以添加吗？

- Fravadona

1

“of order 2” 是什么意思？为什么你的一些重组是大小为4、3和2的？ - undefined

2

他说他的组合是由(1, 2, 3, 4)选2，(3, 4, 5)选2和(5, 6)选2组成的。 - undefined

1

总是有一种简单的重新组合方式，就是说每对都选择2个，但更有趣的问题是如何得到最稀疏的答案。 - undefined

3

如果我理解正确的话，听起来你想要找到底层组合元素集合的所有子集 S，使得 S 中的每对元素都出现在 input 中，并且不能添加任何元素到 S 中而仍然保持这个属性。是这样吗？如果是的话，这就是在图中找到所有最大团的问题，你可以直接使用 NetworkX 解决这个问题。 - undefined

1

我认为你只需要用蛮力法来解决这个问题，点击这里可以找到数学推导和Python实现的通用公式。 - undefined

显示剩余9条评论

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Grismar · Accepted 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。