How to calculate combinations of pairs of n-wire nodes?

Question

I have a question, suppose I have 3 wires which can be connected to input and output nodes 'a', 'b' and 'c', and the combination number of wire pairings needs to be calculated and returned.

By manually trying to solve this it appears that the combination number is simply the factorial of the wire number, or 3!, like in the following example:

I'm interested in an algorithmic approach though (in Python) to solve it for bigger numbers, however, my programming skills are pretty terrible as of now...

So I tried to initialize two tuples with the names of the inputs/outputs: (Maybe I should use sets instead because the order doesn't matter?)

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

But now I have no idea what next, I tried different methods with nested for-loops but I can't seem to get the correct results.

The output of the program in this case should return me lists with the combinations, something like the following:

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

Thank you again, I'd be very thankful for any help, and excuse me if the question is silly...

It is not really clear what you are asking. Is it the algorithm you have trouble with? Which algorithm? Are you seeking to find an algorithm for a specific problem (torn cables?) or do you want an algorithm for combination generation? Or, maybe you know the algorithm and interested in a program. What language? Python? Javascript? Have you tried implementing the algorithm yourself? Please see [how to ask](http://stackoverflow.com/help/how-to-ask) — jrook, Feb 04 '20 at 19:00
What is the issue, exactly? As @jrook said, we're missing a lot of information. — AMC, Feb 04 '20 at 22:21

score 1 · Answer 1 · answered Feb 04 '20 at 18:56

This will give you the result you are expecting :

#!/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)

Let me know if it works for you.

score 1 · Answer 2 · answered Feb 04 '20 at 19:11

You want permutations, not combinations. The hard work can be done by itertools; the only other thing to do is output formatting.

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)
    ]

Example:

>>> 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']]

If you really want each string in its own list, change '%s <-> %s' % pair to ['%s <-> %s' % pair] in the list comprehension.

If you are particularly interested in how the itertools.permutations algorithm generates the permutations in the first place, you can read the sample code in the docs. There are several other standard algorithms for generating permutations, and many good Q&As on Stack Overflow about those algorithms.

How to calculate combinations of pairs of n-wire nodes?

2 Answers2