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


  • $\begingroup$ 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. $\endgroup$ – Yuval Filmus Feb 6 '19 at 8:16
  • $\begingroup$ 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 ? $\endgroup$ – MS. Feb 6 '19 at 8:22
  • $\begingroup$ Let me repeat the question. Will you be happy with an algorithm that enumerates all partitions of $\{1,\ldots,2n\}$ into pairs? $\endgroup$ – Yuval Filmus Feb 6 '19 at 8:24
  • $\begingroup$ yes i am asking for it . Can you please help about this if you have any idea? $\endgroup$ – MS. Feb 6 '19 at 8:25
  • $\begingroup$ thank you for classifying my problem. $\endgroup$ – MS. Feb 6 '19 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.


  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. $$

| cite | improve this answer | |
  • $\begingroup$ 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/… $\endgroup$ – MS. Feb 6 '19 at 9:24
  • $\begingroup$ You'd have to be more specific with what you don't understand. $\endgroup$ – Yuval Filmus Feb 6 '19 at 9:27

Not the answer you're looking for? Browse other questions tagged or ask your own question.