Finding combinations of pairs (connections)

Question

I'm interested in Python specifically, but a generic solution would be also be much appreciated. I have an even number of nodes (let's say 12 for a particular example):

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

Each node must be connected to another node, forming 6 connections (pairs). I need to figure out a way to find all possible combinations of connections. Also, 'a1'-'a2' should be considered the the same as 'a2'-'a1'

Some thoughts:

I can get the list of possible itertools.combinations(lst, 2), but nodes are not reusable. Say, a connection 'a1'<->'a2' should eliminate 'a1'<->'a3' from the available choices as 'a1' already used.
I have no idea if the search is even applicable as there seems to be a few problems:
- there seems to be no (easy, cheap) way to track visited states
- the solution will always be on the bottom (need to traverse the tree all the way down to complete all the connections)

You want to find all possible configurations of connections, right? That is, the list [ [1,2], [3,4], ... [11,12] ] represents one configuration and you want to find all possible such lists. — jf328, Jan 16 '17 at 17:17
Is this a directed or undirected graph? For example, is a1-a2 the same as a2-a1? — Greg Glockner, Jan 16 '17 at 17:29
Yes, that's what I'm looking for and a1-a2 is the same as a2-a1 — dccharacter, Jan 16 '17 at 20:03

score 3 · Accepted Answer · answered Jan 16 '17 at 18:29

3

Here is a recursive solution for your problem:

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

The number of all solutions can be calculated accordingly:

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

Note that I didn't check for n % 2 == 0.

Also for n==len(l)==12 you'll get 10395 possible sets of combinations which is quite doable. But this code, while being short and readable, is gernerating and regenerating lists and tuples over and over again which makes it slow.
See if it's fast enough for you, otherwise we'll have to tweak it.

answered Jan 16 '17 at 18:29

swenzel

6,745
3
23
37

It's weird, I'm trying to test it and it works properly if I do print list(findPairs(l)), but if I do print findPairs(l).next() it gives only the very first configuration :-( – dccharacter Jan 16 '17 at 22:03
That's because it returns a [generator](https://wiki.python.org/moin/Generators). `list(findPairs(l))` is probably what you need, unless you're trying to find all combinations for a list with 18 Nodes which would take very long. That's what generators are for. – swenzel Jan 16 '17 at 22:27
Yes, I know this is a generator. So next() function is supposed to fetch the next item from the generator. And it doesn't, it keeps returning the very first combination as if something resets it. – dccharacter Jan 16 '17 at 22:29
Anyway, I worked around it. Gosh, it was indeed 10395 combinations! You are a magician. And I learned there's no solution for my task on this case :-) – dccharacter Jan 16 '17 at 22:36
1

I suppose you're doing something like `next(findPairs(l))`. This way you'll always call `next` on a freshly created generator which indeed only fetches the first element. You need to save the generator to a variable (e.g. `pairGen`) and then call `next(pairGen)` repeatedly ;) – swenzel Jan 16 '17 at 22:40
Oh, what a genius I am! Thanks much! – dccharacter Jan 17 '17 at 00:04

score 1 · Answer 2 · edited May 23 '17 at 12:25

1

I think you just need to use permutations and take adjacent pairs, then remove any reversed order duplicates:

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)

So how does this work?

We need to loop over every permutation of the nodes:

for perm in itertools.permutations(nodes):

Then create pairs from adjacent nodes in the permutation:

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

This is done via taking two adjacent nodes and sorting them so we can look for dupes later:

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

and then creating a tuple so that we have something immutable to allow indexing. Then take all of the pairs for one permutation and perform the same sort and conversion to tuple for the entire permutation:

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

Then add the permutation to a set, which removes duplicates:

perms.add(p)

And print the results:

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

edited May 23 '17 at 12:25

Community

1
1

answered Jan 16 '17 at 17:17

Stephen Rauch

47,830
31
106
135

1

But you will have duplicates. 'A1A2, B1B2' is the same as 'A2A1, B2B1'. For 4 nodes, only '12, 34', '13, 24', '14, 23' are unique. Taking all permutation then filter seems order of magnitude too slow. (But I have no idea how to do it efficiently either) – jf328 Jan 16 '17 at 17:22
This one works, but it's too slow :-) It also hangs for quite a while after each 944 attempts. I guess that's when it goes through "reversed" pairs. – dccharacter Jan 16 '17 at 20:51
@dccharacter, It maybe slow, but it was fast to write, and it is good to have a working reference, while trying to make it faster. :-) – Stephen Rauch Jan 16 '17 at 21:01
Oh, that's absolutely true and I appreciate it a lot! I'm trying to figure out how it works though :-D – dccharacter Jan 16 '17 at 21:26
1

So I just added some explanation of the workings. Hopefully it is useful. – Stephen Rauch Jan 16 '17 at 21:48

Finding combinations of pairs (connections)

2 Answers2