> 백엔드 개발 > 파이썬 튜토리얼 > 그래프 이론을 사용하여 요소가 겹치는 목록을 병합하는 방법은 무엇입니까?

그래프 이론을 사용하여 요소가 겹치는 목록을 병합하는 방법은 무엇입니까?

Susan Sarandon
풀어 주다: 2024-10-21 17:14:02
원래의
199명이 탐색했습니다.

How to Merge Lists with Overlapping Elements Using Graph Theory?

공유 요소와 목록 병합: 그래프 이론적 접근법

목록 모음 중 일부에 중복되는 요소가 포함되어 있는 경우 목표는 다음과 같습니다. 원래 목록 전체의 고유 요소 전체 세트로 구성된 목록 세트로 통합하는 것입니다. 예를 들어, 다음 목록 입력 목록을 고려해 보세요.

L = [['a', 'b', 'c'], ['b', 'd', 'e'], ['k'], ['o', 'p'], ['e', 'f'], ['p', 'a'], ['d', 'g']]
로그인 후 복사

작업은 더 이상 목록을 결합할 수 없을 때까지 공통 요소를 공유하는 목록을 병합하는 것입니다. 원하는 출력은 다음과 같습니다.

L = [['a', 'b', 'c', 'd', 'e', 'f', 'g', 'o', 'p'], ['k']]
로그인 후 복사

부울 연산과 while 루프를 사용할 수도 있지만 목록을 그래프로 보면 더 효율적인 접근 방식을 찾을 수 있습니다. 그래프 표현에서 각 목록은 모서리로 연결된 노드 집합에 해당합니다. 따라서 문제는 이 그래프 내에서 연결된 구성 요소를 찾는 것입니다.

한 가지 솔루션은 아래에 설명된 것처럼 그래프 분석을 위한 강력한 라이브러리인 NetworkX를 활용하는 것입니다.

<code class="python">import networkx 
from networkx.algorithms.components.connected import connected_components

def to_graph(l):
    G = networkx.Graph()
    for part in l:
        # each sublist is a bunch of nodes
        G.add_nodes_from(part)
        # it also imlies a number of edges:
        G.add_edges_from(to_edges(part))
    return G

def to_edges(l):
    """ 
        treat `l` as a Graph and returns it's edges 
        to_edges(['a','b','c','d']) -> [(a,b), (b,c),(c,d)]
    """
    it = iter(l)
    last = next(it)

    for current in it:
        yield last, current
        last = current    

G = to_graph(l)
print(connected_components(G))
# prints [['a', 'c', 'b', 'e', 'd', 'g', 'f', 'o', 'p'], ['k']]</code>
로그인 후 복사

그래프 이론의 NetworkX는 작업을 효과적으로 처리하여 정확성과 효율성을 보장합니다.

위 내용은 그래프 이론을 사용하여 요소가 겹치는 목록을 병합하는 방법은 무엇입니까?의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!

원천:php
본 웹사이트의 성명
본 글의 내용은 네티즌들의 자발적인 기여로 작성되었으며, 저작권은 원저작자에게 있습니다. 본 사이트는 이에 상응하는 법적 책임을 지지 않습니다. 표절이나 침해가 의심되는 콘텐츠를 발견한 경우 admin@php.cn으로 문의하세요.
저자별 최신 기사
인기 튜토리얼
더>
최신 다운로드
더>
웹 효과
웹사이트 소스 코드
웹사이트 자료
프론트엔드 템플릿