dữ liệu trong một danh sách trong danh sách

Question

Cho rằng:

g=[[], [], [0, 2], [1, 5], [0, 2, 3, 7], [4, 6], [1, 4, 5, 6], [], [], [3, 7]] 

Làm thế nào tôi có thể so sánh mỗi danh sách trong g để cho các danh sách chia sẻ bất cứ số chung có thể hợp nhất với một bộ?

ví dụ:
0 tồn tại trong g[2] và g[4] để họ hợp nhất cho một bộ {0,2,3,7}

Tôi đã thử những điều sau nhưng nó không hoạt động:

for i in g: 
    for j in g: 
     if k in i == l in j: 
      m=set(i+j) 

Tôi muốn làm cho các thiết lập lớn nhất có thể.

Answer 1

Dưới đây là một quickie mà sẽ cung cấp một danh sách các tất cả bộ mà giao nhau:

sets = [set(i+j) for i in g for j in g if i!=j and (set(i) & set(j))] 

Lưu ý rằng mỗi kết quả sẽ được lặp lại, vì mỗi danh sách đang được so sánh hai lần, một lần ở bên trái và một lần Phía bên phải.

Answer 2

Là nhanh hơn nhiều cách Trước tiên bạn có thể tạo danh sách các bộ mặt hàng có nhiều hơn một (s). sau đó đi qua danh sách của bạn và cập nhật tại chỗ với chức năng union!

s=map(set,g) 
def find_intersection(m_list): 
    for i,v in enumerate(m_list) : 
     for j,k in enumerate(m_list[i+1:],i+1): 
      if v & k: 
       m_list[i]=v.union(m_list.pop(j)) 
       return find_intersection(m_list) 
    return m_list 

Demo:

g=[[], [], [0, 2], [1, 5], [0, 2, 3, 7], [4, 6], [1, 4, 5, 6], [], [], [3, 7]] 
s=map(set,g) 
print find_intersection(s) 

[set([0, 2, 3, 7]), set([1, 4, 5, 6])] 

g=[[1,2,3],[3,4,5],[5,6],[6,7],[9,10],[10,11]] 
s=map(set,g) 
print find_intersection(s) 

[set([1, 2, 3, 4, 5, 6, 7]), set([9, 10, 11])] 

g=[[], [1], [0,2], [1, 5], [0, 2, 3, 7], [4, 6], [1, 4, 5, 6], [], [], [3, 7]] 
s=map(set,g) 
print find_intersection(s) 

[set([1, 4, 5, 6]), set([0, 2, 3, 7])] 

Benchmark với @ câu trả lời của Mark:

from timeit import timeit 


s1="""g=[[], [], [0, 2], [1, 5], [0, 2, 3, 7], [4, 6], [1, 4, 5, 6], [], [], [3, 7]] 
sets = [set(i+j) for i in g for j in g if i!=j and (set(i) & set(j))] 
    """ 
s2="""g=[[], [], [0, 2], [1, 5], [0, 2, 3, 7], [4, 6], [1, 4, 5, 6], [], [], [3, 7]] 

s=map(set,g) 

def find_intersection(m_list): 
    for i,v in enumerate(m_list) : 
     for j,k in enumerate(m_list[i+1:],i+1): 
      if v & k: 
       s[i]=v.union(m_list.pop(j)) 
       return find_intersection(m_list) 
    return m_list 
    """ 

print ' first: ' ,timeit(stmt=s1, number=100000) 
print 'second : ',timeit(stmt=s2, number=100000) 

first: 3.8284008503 
second : 0.213887929916 

Answer 3

Nếu g hoặc g yếu tố 's là rất lớn, bạn có thể sử dụng rời nhau Sets để thúc đẩy hiệu quả.

Cấu trúc dữ liệu này có thể được sử dụng để phân loại từng phần tử vào tập hợp phần tử.

Bước đầu tiên là xây dựng một bộ sưu tập với tất cả g bộ dán nhãn bởi chỉ mục của họ rời nhau Set trong g:

g=[[], [], [0, 2], [1, 5], [0, 2, 3, 7], [4, 6], [1, 4, 5, 6], [], [], [3, 7],[99]] 
g = map(set, g) 
dss = CDisjointSets() 
for i in xrange(len(g)): 
    dss.MakeSet(i) 

Sau đó, các bộ được tham gia bất cứ khi nào ngã tư là không có sản phẩm nào:

for i in xrange(len(g)): 
    for j in xrange(i+1, len(g)): 
     if g[i].intersection(g[j]): 
      dss.Join(i,j) 

Tại thời điểm này, dss sẽ cung cấp cho bạn nhãn chung cho các bộ g nên ghép lại với nhau:

print(dss) 

mẹ (0) = 0 mẹ (1) = 1 mẹ (2) = 2 mẹ (3) = 3 mẹ (4) = 2 mẹ (5) = 3 mẹ (6) = 3 mẹ (7) = 7 mẹ (8) = 8 mẹ (9) = 2 mẹ (10) = 10

Bây giờ bạn chỉ phải xây dựng các bộ mới tham gia những người mà có cùng nhãn:

l2set = dict() 
for i in xrange(len(g)): 
    label = dss.FindLabel(i).getLabel() 
    l2set[label] = l2set.get(label, set()).union(g[i]) 
print(l2set) 

Hệ quả là:

{0: set([]), 1: set([]), 2: set([0, 2, 3, 7]), 3: set([1, 4, 5, 6]), 7: set([]), 8: set([]), 10: set([99])} 

này là việc thực hiện của các tập hợp không giao nhau tôi đã sử dụng nhưng chắc chắn bạn có thể tìm anotherone với một sintax tốt hơn:

""" Disjoint Sets 
    ------------- 
    Pablo Francisco Pérez Hidalgo 
    December,2012. """ 
class CDisjointSets: 

    #Class to represent each set 
    class DSet: 
     def __init__(self, label_value): 
      self.__label = label_value 
      self.rank = 1 
      self.parent = self 
     def getLabel(self): 
      return self.__label 

    #CDisjointSets Private attributes 
    __sets = None 

    #CDisjointSets Constructors and public methods. 
    def __init__(self): 
     self.__sets = {} 

    def MakeSet(self, label): 
     if label in self.__sets: #This check slows the operation a lot, 
      return False   #it should be removed if it is sure that 
           #two sets with the same label are not goind 
           #to be created. 
     self.__sets[label] = self.DSet(label) 

    #Pre: 'labelA' and 'labelB' are labels or existing disjoint sets. 
    def Join(self, labelA, labelB): 
     a = self.__sets[labelA] 
     b = self.__sets[labelB] 
     pa = self.Find(a) 
     pb = self.Find(b) 
     if pa == pb: 
      return #They are already joined 
     parent = pa 
     child = pb 
     if pa.rank < pb.rank: 
      parent = pb 
      child = pa 
     child.parent = parent 
     parent.rank = max(parent.rank, child.rank+1) 

    def Find(self,x): 
     if x == x.parent: 
      return x 
     x.parent = self.Find(x.parent) 
     return x.parent 

    def FindLabel(self, label): 
     return self.Find(self.__sets[label]) 

    def __str__(self): 
     ret = "" 
     for e in self.__sets: 
      ret = ret + "parent("+self.__sets[e].getLabel().__str__()+") = "+self.FindLabel(e).parent.getLabel().__str__() + "\n" 
     return ret