I’m working on a program to solve the Chinese Postman Problem and am currently focusing on generating all possible pairings of odd vertices in a graph. My goal is to find the optimal pairing of these vertices to minimize the total distance of the added edges.
Given an even number 𝑛 of odd vertices, such as a, b, c, d, e, f, I need to get all possible pairings or partitions, such as:
(a,b),(c,d),(e,f)
(a,b),(c,e),(d,f)
(a,b),(c,f),(d,e)
For each pairing, I’ll calculate the shortest path between each pair, sum these distances, and select the pairing with the smallest total distance.
I initially attempted to develop an algorithm to generate these pairings, starting with all vertices sorted and selecting pairs iteratively. However, I encountered issues ensuring that all valid partitions were generated.
My specific challenges are:
I need an efficient way to get all possible pairings (or perfect matchings) of the odd vertices. My current approach is not producing all possible pairings, especially when dealing with larger sets of vertices.
Is there a known algorithm or approach for generating all possible pairings of a given set of vertices?
1
Here’s one:
def splitIntoPairs( src, sofar=[] ):
if src==[]:
yield sofar
for i,x in enumerate(src[:1]):
for j,y in enumerate(src[i+1:]):
for z in splitIntoPairs( src[:i]+src[i+1:i+j+1]+src[i+1+j+1:] , sofar+[(x,y)] ):
yield z
For your example, it yields:
[('a', 'b'), ('c', 'd'), ('e', 'f')]
[('a', 'b'), ('c', 'e'), ('d', 'f')]
[('a', 'b'), ('c', 'f'), ('d', 'e')]
[('a', 'c'), ('b', 'd'), ('e', 'f')]
[('a', 'c'), ('b', 'e'), ('d', 'f')]
[('a', 'c'), ('b', 'f'), ('d', 'e')]
[('a', 'd'), ('b', 'c'), ('e', 'f')]
[('a', 'd'), ('b', 'e'), ('c', 'f')]
[('a', 'd'), ('b', 'f'), ('c', 'e')]
[('a', 'e'), ('b', 'c'), ('d', 'f')]
[('a', 'e'), ('b', 'd'), ('c', 'f')]
[('a', 'e'), ('b', 'f'), ('c', 'd')]
[('a', 'f'), ('b', 'c'), ('d', 'e')]
[('a', 'f'), ('b', 'd'), ('c', 'e')]
[('a', 'f'), ('b', 'e'), ('c', 'd')]