튜플에서의 패턴 찾기 Python

Question

튜플에 저장된 정수 쌍 (예 : (1,2) (4,5) ...)이 있습니다. 이 튜플은 목록에 저장됩니다.

나는이 튜플들 중에서 어떤 종류의 정수로 시작하여 다음 튜플의 두 번째 정수에서 다른 튜플의 첫 번째 점프로 점령되는이 종류의 패턴 (1,2) (2,3) (3,4) (4,1)을 찾고자한다. 픽업 된 정수로 끝난다. 처음에는

각 패턴은 세트로 저장됩니다. 그런 다음 첫 번째 정수와 관련 패턴을 키/값 쌍으로 저장합니다. 내 예를 들면 다음과 같습니다. dictionary={1:set([1,2,3,4]),...}

그런 다음 항목이 공통된 패턴을 병합합니다. 예를 들어 (1,2) (2,3) (3,1)과 (2,4) (4,1)은이 집합으로 병합됩니다 : set ([1,2,3,4]). 그리고 열쇠 ​​중 하나를 삭제합니다. 나는 다음과 같은 문제에 직면하고있어

from collections import defaultdict 
dictio_chaine=defaultdict(set) 
for item1 in A:    # A is the list containing the afore mentioned tuples 
    a,b=item1 
    l=[a,b] 
    for item2 in A: 
     if item2[0]==b and b!=a: 
      b=item2[1] 
      l.append(b) 
     if b==a: 
      break 
    if l[-1]==a: 
     dictio_chaine[a].update(l) 

liste=combinations(dictio_chaine.iterkeys(),2) #The following piece of code merges the 
for item in liste:           #overlapping patterns. 
    if item[0] in dictio_chaine and item[1] in dictio_chaine: 
     if dictio_chaine[item[0]]&dictio_chaine[item[1]]: 
      dictio_chaine[item[0]].update(dictio_chaine[item[1]]) 
      del dictio_chaine[item[1]] 

: 여기

내 코드 튜플의리스트에서 패턴을 찾아 내 알고리즘의 첫 번째 부분의 성능은 O에 있기 때문에 매우 불량 (n^2).

나는 나무를 만드는 것이 더 좋을 것이라고 생각한다. 패턴 (2,5) (5,2)가 발생하면되는 패턴 (1,2) (2,3) (3,1)는 2 is the child of 1, 3 is the child of 2 ...

다음에, 나는 같은과 한 세트의 가지에 병합 것, 새로운 지점 5 결국 이미 1의 아들 (2)의 자식 인이된다 첫 번째 노드로 남는다.

더 좋을까요? 어떻게하면 쉽게 구현할 수있는 트리는 내가하려고하는 것에 전혀 맞지 않는 이진 트리입니다.

알고리즘 개선에 도움이되는 조언이 있으십니까?

Answer 1

내가이 질문을 이해한다면, 당신은 유향 그래프에서 간단한주기를 찾으려하고있다.

다른 말로하면, (4,5)와 같은 튜플을 노드 4와 노드 5 사이의 방향성을 나타내는 에지로 해석 할 수 있습니다. 노드에서 시작하여 다음과 같은 번호를 따르는 경로를 찾으려고합니다. 이 엣지들은 시작 노드로 돌아 간다.

파이썬 라이브러리 NetworkX에있는 simple_cycles 함수를 사용하면 쉽게이 작업을 수행 할 수 있습니다. 예를 들어,

>>> import networkx as nx 
>>> G = nx.DiGraph([(0, 0), (0, 1), (0, 2), (1, 2), (2, 0), (2, 1), (2, 2)]) 
>>> list(nx.simple_cycles(G)) 
[[2], [2, 1], [2, 0], [2, 0, 1], [0]] 

시간 복잡도는 O ((N + E) (c + 1)) n 개의 노드, 즉 에지 및 C 기본 회로.