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$
  • $\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

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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