Поиск комбинаций пар (соединений)

Question

Меня интересует только Python, но также будет оценено общее решение. У меня есть четное число узлов (скажем, 12 для конкретного примера):

[ 'a1', 'a2', 'a3', 'b1', 'b2', 'b3', «c1 ',' c2 ',' c3 ',' d1 ',' d2 ',' d3 ']

Каждый узел должен быть подключен к другому узлу, образуя 6 соединений (пары). Мне нужно выяснить, как найти все возможные комбинации соединений. Кроме того, 'a1'-'a2' следует рассматривать так же, как 'a2'-'a1'

Некоторые мысли:

• я могу получить список возможных itertools.combinations(lst, 2), но узлы не подлежит повторному использованию. Скажем, соединение 'a1'<->'a2' должно устранить 'a1'<->'a3' из доступных вариантов, поскольку 'a1' уже используется.

• Я понятия не имею, если поиск даже применимо, как кажется, есть несколько проблем:

  • там, кажется, нет (легкий, дешевый) способ отслеживать посещенные состояния
  • решение всегда будет на день (нужно перемещаться по дереву всех вплоть до завершения всех соединений)

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 

Число всех решений может быть вычислен соответственно:

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

Обратите внимание, что я не проверял на n % 2 == 0.

Также для 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) 

Так как же это работает?

Нам нужно перебрать каждую перестановку узлов:

for perm in itertools.permutations(nodes): 

Затем создают пары из соседних узлов в перестановке:

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

Это делается с помощью взятия двух соседних узлов и сортировок их так, чтобы мы могли искать дубликатов позже:

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

, а затем создайте tuple, чтобы у нас было что-то immutable, чтобы разрешить индексирование.Затем возьмите все пары для одной перестановки и выполняет те же sort и преобразование в tuple для всей перестановки:

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

Затем добавить перестановку в set, которая удаляет дубликаты:

perms.add(p) 

И распечатать результаты:

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