Как рассчитать комбинации пар n-проводных узлов? - PullRequest
Новая
       12

Как рассчитать комбинации пар n-проводных узлов?

0 голосов
/ 04 февраля 2020

У меня есть вопрос, предположим, у меня есть 3 провода, которые можно подключить к входным и выходным узлам 'a', 'b' и 'c', и необходимо вычислить и вернуть комбинационное число парных соединений проводов.

Попытка решить эту проблему вручную показывает, что номер комбинации является просто факториалом номера провода, или 3! , как в следующем примере:

Wire Combinations

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

Поэтому я попытался инициализировать два кортежа с именами входов / выходов: (Может быть, я должен использовать наборы вместо этого, потому что порядок не имеет значения?) 

inputs = ('a', 'b', 'c')
outputs = ('a', 'b', 'c')

Но теперь я понятия не имею, что дальше, я пробовал разные методы с вложенными циклами for, но я не могу получить правильные результаты.

Вывод программы в этом случае должен вернуть мне списки с комбинациями, почему-то вот так: 

1. [['a <-> a'], ['b <-> b'], ['c <-> c']]
2. [['a <-> a'], ['b <-> c'], ['c <-> b']]
3. [['a <-> c'], ['b <-> b'], ['c <-> a']]
4. [['a <-> b'], ['b <-> a'], ['c <-> c']]
5. [['a <-> b'], ['b <-> c'], ['c <-> a']]
6. [['a <-> c'], ['b <-> a'], ['c <-> b']]
Number of combinations: 6

Еще раз спасибо, я был бы очень благодарен за любую помощь, и извините, если вопрос глупый ...

Ответы [ 2 ]

1 голос
/ 04 февраля 2020

Вы хотите перестановок , а не комбинаций . Тяжелая работа может быть сделана itertools; единственное, что нужно сделать - это форматирование вывода. 

from itertools import permutations
from string import ascii_lowercase

def wire_permutations(n):
    if n < 0 or n > len(ascii_lowercase):
        raise ValueError()

    letters = ascii_lowercase[:n]
    return [
        ['%s <-> %s' % pair for pair in zip(letters, perm)]
        for perm in permutations(letters)
    ]

Пример: 

>>> wire_permutations(3)
[['a <-> a', 'b <-> b', 'c <-> c'],
 ['a <-> a', 'b <-> c', 'c <-> b'],
 ['a <-> b', 'b <-> a', 'c <-> c'],
 ['a <-> b', 'b <-> c', 'c <-> a'],
 ['a <-> c', 'b <-> a', 'c <-> b'],
 ['a <-> c', 'b <-> b', 'c <-> a']]

Если вы действительно хотите, чтобы каждая строка была в своем собственном списке, измените '%s <-> %s' % pair на ['%s <-> %s' % pair] в понимание списка.

Если вам особенно интересно, как алгоритм itertools.permutations генерирует перестановки, вы можете прочитать образец кода в документации. Есть несколько других стандартных алгоритмов для генерации перестановок, и много хороших вопросов и ответов по переполнению стека об этих алгоритмах.

1 голос
/ 04 февраля 2020

Это даст вам ожидаемый результат: 

#!/usr/local/bin/python3

inputs = ('a', 'b', 'c')
outputs = ('a', 'b', 'c')


result = []
for l in inputs:
    for sl in outputs:
        result.append([ "{}{}{}".format(l," <-> ",sl)])
        result.append([ "{}{}{}".format(sl," <-> ",l)])

print(result)

Дайте мне знать, работает ли он для вас.

...