Quiero agrupar las tuplas en base a atributos similares

Tengo una lista de tuplas. [(1, 2), (2, 3), (4, 3), (5, 6), (6, 7), (8, 2)]

Quiero agruparlos en listas en función de las tuplas que están conectadas (tienen valores relacionados).

Entonces, el resultado final son dos listas de valores de tupla relacionados = [[1, 2, 3, 4, 8], [5, 6, 7]]

¿Cómo puedo escribir una función para hacer esto? Esta fue una pregunta de entrevista de trabajo. Estaba intentando hacerlo en Python, pero estoy frustrado y solo quiero ver la lógica detrás de la respuesta, así que incluso el código psuedo me ayudaría, así puedo ver lo que hice mal.

Solo tuve unos minutos para hacer esto en el lugar, pero esto es lo que intenté:

def find_partitions(connections): theBigList = [] # List of Lists list1 = [] # The initial list to store lists theBigList.append(list1) for list in theBigList: list.append(connection[1[0], 1[1]]) for i in connections: if i[0] in list or i[1] in list: list.append(i[0], i[1]) else: newList = [] theBigList.append(newList) 

Esencialmente, el chico quería una lista de listas de valores que estaban relacionados. Intenté usar un bucle for, pero me di cuenta de que no funcionaría, y luego el tiempo se agotó.

A medida que completamos los componentes, en cada etapa hay tres casos a considerar (ya que tendrá que hacer coincidir los grupos superpuestos):

  1. Ni x ni y están en ningún componente ya encontrado.
  2. Ambos ya están en conjuntos diferentes , x en set_i e y en set_j.
  3. Uno o ambos están en un componente, x en set_i o y en un set_i.

Podemos usar el set incorporado para ayudar. (Vea los ejemplos más complicados de @jwpat y de @ DSM) :

 def connected_components(lst): components = [] # list of sets for (x,y) in lst: i = j = set_i = set_j = None for k, c in enumerate(components): if x in c: i, set_i = k, c if y in c: j, set_j = k, c #case1 (or already in same set) if i == j: if i == None: components.append(set([x,y])) continue #case2 if i != None and j != None: components = [components[k] for k in range(len(components)) if k!=i and k!=j] components.append(set_i | set_j) continue #case3 if j != None: components[j].add(x) if i != None: components[i].add(y) return components lst = [(1, 2), (2, 3), (4, 3), (5, 6), (6, 7), (8, 2)] connected_components(lst) # [set([8, 1, 2, 3, 4]), set([5, 6, 7])] map(list, connected_components(lst)) # [[8, 1, 2, 3, 4], [5, 6, 7]] connected_components([(1, 2), (4, 3), (2, 3), (5, 6), (6, 7), (8, 2)]) # [set([8, 1, 2, 3, 4]), set([5, 6, 7])] # @jwpat's example connected_components([[1, 3], [2, 4], [3, 4]] # [set([1, 2, 3, 4])] # @DSM's example 

Este ciertamente no será el método más eficiente, pero quizás sea uno similar a lo que ellos esperarían. Como señala Jon Clements, hay una biblioteca para este tipo de cálculos: networkx , donde serán mucho más eficientes.

 l = [ (1, 2), (2, 3), (4, 3), (5, 6), (6, 7), (8, 2) ] # map each value to the corresponding connected component d = {} for i, j in l: di = d.setdefault(i, {i}) dj = d.setdefault(j, {j}) if di is not dj: di |= dj for k in dj: d[k] = di # print out the connected components p = set() for i in d.keys(): if i not in p: print(d[i]) p |= d[i] 

Esto ciertamente no es elegante, pero funciona:

 def _grouper(s,ll): for tup in ll[:]: if any(x in s for x in tup): for y in tup: s.add(y) ll.remove(tup) def grouper(ll,out=None): _ll = ll[:] s = set(ll.pop(0)) if out is None: out = [s] else: out.append(s) l_old = 0 while l_old != len(_ll): l_old = len(_ll) _grouper(s,_ll) if _ll: return grouper(_ll,out=out) else: return out ll = [ (1, 2), (2, 3), (4, 3), (5, 6), (6, 7), (8, 2) ] print grouper(ll) 

utilizando sets :

 In [235]: def func(ls): new_lis=sorted(sorted(ls),key=min) lis=[set(new_lis[0])] for x in new_lis[1:]: for y in lis: if not set(x).isdisjoint(y): y.update(x);break else:lis.append(set(x)) return lis .....: In [236]: func([(3, 1), (9, 3), (6, 9)]) Out[236]: [set([1, 3, 6, 9])] In [237]: func([[2,1],[3,0],[1,3]]) Out[237]: [set([0, 1, 2, 3])] In [239]: func([(1, 2), (4, 3), (2, 3), (5, 6), (6, 7), (8, 2)]) Out[239]: [set([8, 1, 2, 3, 4]), set([5, 6, 7])] 

Qué tal si

 ts = [(1, 2), (2, 3), (4, 3), (5, 6), (6, 7), (8, 2)] ss = [] while len(ts) > 0: s = set(ts.pop()) ol = 0 nl = len(s) while ol < nl: for t in ts: if t[0] in s or t[1] in s: s = s.union(ts.pop(ts.index(t))) ol = nl nl = len(s) ss.append(s) print ss