CODEWITHSUNDEEP
pythoniterationcombinations
mcfly
mcfly

Reputation: 1151

Find all common elements and combinations in tuples using Python

I am trying to group all values together that share common elements across tuples - essentially find groups of numbers that for any combination of them (no order required) - I have the tuple. For example, if I have the following set of tuples:

(1,2),(1,3),(1,5),(1,6),(2,3),(2,5),(2,7),(3,5),(3,7),(3,9)

I want to understand all the elements that are in common. For this example, this would be:

1, 2, 3, 5  (since I have any combination of 1,2,3 and 5)
2, 3, 7 (since I have any combination of 2,3 and 7)
1, 6 (since I have any combination of 1 and 6)
3, 9 (since I have any combination of 3 and 9)

Any thoughts on how to solve this?

Upvotes: 2

Views: 514

Answers (1)

Eric Duminil
Eric Duminil

Reputation: 54223

As mentioned by @alfasin, you're looking for the maximal cliques in your graph.

A clique, C, in an undirected graph G = (V, E) is a subset of the vertices, C ⊆ V, such that every two distinct vertices are adjacent.

A maximal clique is a clique that cannot be extended by including one more adjacent vertex, that is, a clique which does not exist exclusively within the vertex set of a larger clique.

NetworkX with find_cliques is your friend:

>>> import networkx as nx
>>> G = nx.Graph([(1,2),(1,3),(1,5),(1,6),(2,3),(2,5),(2,7),(3,5),(3,7),(3,9)])
>>> list(nx.find_cliques(G))
[[3, 9], [3, 2, 1, 5], [3, 2, 7], [6, 1]]

If you want to define your graph as the union of small cliques and see if they merge to larger cliques, you can use itertools.combinations to iterate over all the edges of your input cliques and add them to the graph:

import networkx as nx
from itertools import combinations

G = nx.Graph()

cliques = [(1,2,3),(1,2,4),(1,3,4),(2,3,4)]

for clique in cliques:
  for vertices in combinations(clique, r=2):
    G.add_edge(*vertices)

print(list(nx.find_cliques(G)))
# [[1, 2, 3, 4]]

Upvotes: 4

Related Questions