# Enumerating all ways of pairing odd nodes

Can someone provide a brute force pseudocode for finding best connections between odd-degree nodes in the Chinese postman problem mentioned here?

For example, if the odd nodes are $$B,C,D,E$$, the program should output the three pairings

BC,DE; BD,CE; BE,CD.

• It seems that what you're really asking is: enumerate all partitions of $\{1,\ldots,2n\}$ into pairs. This has nothing to do with the route inspection problem. – Yuval Filmus Feb 6 at 8:16
• i mean how can i get unique combinations of pairs with a given odd-numbered vertices list. I think it is a stage to solve route inspection problem , isn't it ? – MS. Feb 6 at 8:22
• Let me repeat the question. Will you be happy with an algorithm that enumerates all partitions of $\{1,\ldots,2n\}$ into pairs? – Yuval Filmus Feb 6 at 8:24
• thank you for classifying my problem. – MS. Feb 6 at 9:20

Your question doesn't have much to do with the route inspection problem. You are looking for all perfect matchings of $$K_{2n}$$ (the complete graph on $$2n$$ vertices), or equivalently, for an algorithm that enumerates all partitions of $$\{1,\ldots,2n\}$$ into pairs. A simple recursive approach is quite efficient:

Input: A non-empty list $$L$$ of even size.

Output: All possible partitions of $$L$$ into pairs.

Algorithm:

1. If $$L = \{a,b\}$$, return $$(a,b)$$.

2. Otherwise, let $$a$$ be an arbitrary element of $$L$$. Go over all elements $$b \in L \setminus \{a\}$$. For each $$b$$, generate (recursively) all perfect matchings of $$L \setminus \{a,b\}$$, and add $$(a,b)$$ to all of them.

The number of perfect matchings is quite large: $$(2n-1) (2n-3) \cdots (1) = \frac{(2n!)}{2^nn!} \sim \frac{\sqrt{4\pi n} (2n/e)^{2n}}{2^n\sqrt{2\pi n}(n/e)^n} = \sqrt{2} \cdot (2n/e)^n.$$

• I am a bit confused with notation. can you please give more explanations for this solution.Btw i have found a solution for my problem , thanks to your classifying the problem ,in here : stackoverflow.com/questions/10568081/… – MS. Feb 6 at 9:24
• You'd have to be more specific with what you don't understand. – Yuval Filmus Feb 6 at 9:27