Biorąc n krotki reprezentujące pary, zwróć listę z połączonymi krotkami

Question

Podano n krotki, pisz funkcję, która zwróci listę z połączonymi wartościami.

przykład:

pairs = [(1,62), 
    (1,192), 
    (1,168), 
    (64,449), 
    (263,449),  
    (192,289), 
    (128,263), 
    (128,345), 
    (3,10), 
    (10,11) 
    ] 

Wynik:

[[1,62,192,168,289], 
[64,449,263,128,345,449], 
[3,10,11]]  

wierzę, może być rozwiązany za pomocą wykresów lub drzew jako struktury danych, tworząc węzły dla każdej wartości i i krawędzie każdej pary z każdym drzewie lub wykres przedstawiający połączone wartości, ale nie znalazłem jeszcze rozwiązania.

Jaki byłby najlepszy sposób produkcji w Pythonie wynik, który daje listę połączonych wartości dla tych par?

Answer 1

Nie wiedziałem, że ten problem ma już nazwę (dzięki avim!), Więc poszedłem naprzód i rozwiązałem to naiwnie.

To rozwiązanie jest nieco podobne do Eli Rose. Postanowiłem ją jednak opublikować, ponieważ jest nieco bardziej efektywny w przypadku dużych list par, ponieważ słownik lists_by_element śledzi listę elementów, dzięki czemu możemy uniknąć iterowania po wszystkich listach i ich elementach za każdym razem, gdy musimy dodać nowy element.

Oto kod:

def connected_tuples(pairs): 
    # for every element, we keep a reference to the list it belongs to 
    lists_by_element = {} 

    def make_new_list_for(x, y): 
     lists_by_element[x] = lists_by_element[y] = [x, y] 

    def add_element_to_list(lst, el): 
     lst.append(el) 
     lists_by_element[el] = lst 

    def merge_lists(lst1, lst2): 
     merged_list = lst1 + lst2 
     for el in merged_list: 
      lists_by_element[el] = merged_list 

    for x, y in pairs: 
     xList = lists_by_element.get(x) 
     yList = lists_by_element.get(y) 

     if not xList and not yList: 
      make_new_list_for(x, y) 

     if xList and not yList: 
      add_element_to_list(xList, y) 

     if yList and not xList: 
      add_element_to_list(yList, x)    

     if xList and yList and xList != yList: 
      merge_lists(xList, yList) 

    # return the unique lists present in the dictionary 
    return set(tuple(l) for l in lists_by_element.values()) 

A oto jak to działa: http://ideone.com/tz9t7m

Answer 2

Możesz go rozwiązać implementując Disjoint Set (Union-Find).

Inicjalizuj strukturę djs ze wszystkimi liczbami. Następnie dla każdej krotki (x,y), zadzwoń pod numer djs.merge(x,y). Teraz dla każdego numeru x utwórz nowy zestaw dla niego djs.sameSet(x,)==false dla dowolnego zestawu y z każdego istniejącego zestawu.

Może that może ci pomóc.

Answer 3

Wygląda na to, że masz wykres (w postaci listy krawędzi), który może nie być cały w jednym kawałku ("połączony") i chcesz go podzielić na części ("komponenty").

Kiedy myślimy o tym w języku grafów, w większości robimy. Możemy przechowywać listę wszystkich składników, które znaleźliśmy tak daleko (będą to zbiory węzłów) i dodać węzeł do zestawu, jeśli jego partner już tam jest. W przeciwnym razie utwórz nowy komponent dla tej pary.

def graph_components(edges): 
    """ 
    Given a graph as a list of edges, divide the nodes into components. 

    Takes a list of pairs of nodes, where the nodes are integers. 
    Returns a list of sets of nodes (the components). 
    """ 

    # A list of sets. 
    components = [] 

    for v1, v2 in edges: 
     # See if either end of the edge has been seen yet. 
     for component in components: 
      if v1 in component or v2 in component: 
       # Add both vertices -- duplicates will vanish. 
       component.add(v1) 
       component.add(v2) 
       break 
     else: 
      # If neither vertex is already in a component. 
      components.append({v1, v2}) 

    return components 

Użyłem dziwne for ... else budowę ze względu na przeprowadzenie tej jednej funkcji - w else zostanie wykonany jeśli break oświadczenie nie zostało osiągnięte podczas for. Wewnętrzna pętla mogłaby równie dobrze być funkcją zwracającą True lub .

---

EDIT: Jak Francis Colas zaznacza, takie podejście jest zbyt chciwy. Oto zupełnie inne podejście (wiele dzięki Edwardowi Mannowi za piękną implementację DFS w wersji this).

Podejście to opiera się na utworzeniu wykresu, a następnie wykonaniu na nim trajektorii, dopóki nie zabraknie nam nieodwiedzonych węzłów. Powinien działać w czasie liniowym (O (n), aby utworzyć wykres, O (n), aby wykonać wszystkie ruchy poprzeczne, i uważam, że O (n) wystarczy, aby wykonać ustawioną różnicę).

from collections import defaultdict 

def dfs(start, graph): 
    """ 
    Does depth-first search, returning a set of all nodes seen. 
    Takes: a graph in node --> [neighbors] form. 
    """ 
    visited, worklist = set(), [start] 

    while worklist: 
     node = worklist.pop() 
     if node not in visited: 
      visited.add(node) 
      # Add all the neighbors to the worklist. 
      worklist.extend(graph[node]) 

    return visited 

def graph_components(edges): 
    """ 
    Given a graph as a list of edges, divide the nodes into components. 
    Takes a list of pairs of nodes, where the nodes are integers. 
    """ 

    # Construct a graph (mapping node --> [neighbors]) from the edges. 
    graph = defaultdict(list) 
    nodes = set() 

    for v1, v2 in edges: 
     nodes.add(v1) 
     nodes.add(v2) 

     graph[v1].append(v2) 
     graph[v2].append(v1) 

    # Traverse the graph to find the components. 
    components = [] 

    # We don't care what order we see the nodes in. 
    while nodes: 
     component = dfs(nodes.pop(), graph) 
     components.append(component) 

     # Remove this component from the nodes under consideration. 
     nodes -= component 

    return components 

Answer 4

Innym rozwiązaniem, które jest bardziej kompaktowy niż wilka ale obsługuje scalania wbrew Eli:

def connected_components(pairs): 
    components = [] 
    for a, b in pairs: 
     for component in components: 
      if a in component: 
       for i, other_component in enumerate(components): 
        if b in other_component and other_component != component: # a, and b are already in different components: merge 
         component.extend(other_component) 
         components[i:i+1] = [] 
         break # we don't have to look for other components for b 
       else: # b wasn't found in any other component 
        if b not in component: 
         component.append(b) 
       break # we don't have to look for other components for a 
      if b in component: # a wasn't in in the component 
       component.append(a) 
       break # we don't have to look further 
     else: # neither a nor b were found 
      components.append([a, b]) 
    return components 

Zauważ, że Opieram się na wyłamywaniu pętli, gdy znajduję element w komponencie, dzięki czemu mogę użyć klauzuli else do obsługi przypadku, w którym ele nie są jeszcze w żadnym komponencie (else jest wykonywany, jeśli pętla zakończyła się bez break).