1
$\begingroup$

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.

$\endgroup$

marked as duplicate by xskxzr, David Richerby, Evil, Yuval Filmus algorithms Mar 8 at 21:16

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\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 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 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 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 at 8:25
  • $\begingroup$ thank you for classifying my problem. $\endgroup$ – MS. Feb 6 at 9:20
0
$\begingroup$

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

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

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