쌍 (연결)의 조합 찾기

Question

저는 파이썬에 특별히 관심이 있지만 일반 솔루션도 크게 감사하겠습니다. I 노드 수가 짝수가 (의 특정 예 12라고하자)

[ "A1", "A2", "A3", "B1", "B2", "B3", "C1을 'd2', 'd3']

각 노드는 6 개의 연결 (쌍)을 형성하는 다른 노드에 연결되어야합니다. 가능한 모든 연결 조합을 찾는 방법을 찾아야합니다.

• 내가 할 수 itertools.combinations(lst, 2)의 목록을 얻을 수 있지만, 노드는 다시 사용할 수 없습니다 : 또한, 'a1'-'a2'는 'a2'-'a1'

  어떤 생각으로 동일하게 고려되어야한다. 예를 들어, 'a1'<->'a2' 연결은 이미 사용 된 'a1'으로 사용 가능한 선택에서 'a1'<->'a3'을 제거해야합니다.

  • 방문 상태
  • 솔루션을 추적 할 (쉽고, 싼) 방법이없는 것 같다 : 검색은 몇 가지 문제가있을 것 같습니다로도 적용 할 경우

  • 는 나도 몰라 항상 바닥에있을 것입니다 당신이 단지 페이지를 사용할 필요가 있다고 생각

Answer 1

다음은 문제를 재귀 적으로 해결 한 해결책입니다.

def findPairs(l): 
    # recursion anchor, basic case: 
    # when we have 2 nodes only one pair is possible 
    if len(l) == 2: 
     yield [tuple(l)] 
    else: 
     # Pair the first node with all the others 
     for i in range(1, len(l)): 
      # Current pair 
      pair1 = [(l[0], l[i])] 
      # Combine it with all pairs among the remaining nodes 
      remaining = l[1:i] + l[i+1:] 
      for otherPairs in findPairs(remaining): 
       yield pair1 + otherPairs 

모든 솔루션의 수는 그에 따라 계산 될 수있다 : 나는 n % 2 == 0 확인하지 않았다

def N(n): 
    if n == 2: 
     return 1 
    return (n-1) * N(n-2) 

참고.

n==len(l)==12 또한 10395 개의 가능한 조합을 얻을 수 있습니다. 그러나이 코드는 짧고 읽기 쉽지만 목록과 튜플을 반복해서 생성하여 재생성하므로 속도가 느려집니다.
충분히 빠르지 않으면 그렇지 않으면 조정해야합니다.

Answer 2

(모든 연결을 완료하기 위해 아래 나무 모든 에게 길을 통과해야합니다) ermutations 및 take adjacent pairs 후 는 역순 중복 제거 :

nodes = 'A1 A2 B1 B2 C1 C2'.split() 
perms = set() 
for perm in itertools.permutations(nodes): 
    p = tuple(sorted(
     [tuple(sorted(perm[i:i + 2])) for i in range(0, len(perm), 2)])) 
    perms.add(p) 

for perm in sorted(perms): 
    print(perm) 

그래서이 작업을 수행하는 방법? 이 두 개의 인접한 노드를 복용하고 정렬을 통해 이루어집니다

[tuple(sorted(perm[i:i + 2])) for i in range(0, len(perm), 2)] 

:

for perm in itertools.permutations(nodes): 

그런 다음 순열에 인접한 노드의 쌍을 생성합니다

우리는 노드의 모든 순열을 통해 루프 필요 그래서 우리는 나중에 속을 찾을 수 있습니다 :

tuple(sorted(perm[i:i + 2])) 

을 입력 한 다음 tuple을 생성하여 을 입력하여 색인 생성을 허용합니다.이어서 하나의 퍼뮤 테이션에 대해 쌍을 모두 가지고 전체 순열 tuple 동일한 sort 및 전환을 수행

perms.add(p) 

:

p = tuple(sorted(
    [tuple(sorted(perm[i:i + 2])) for i in range(0, len(perm), 2)])) 

그럼 중복을 제거하는 set에 순열 추가 그리고 결과를 인쇄하십시오 :