Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange
2 added 112 characters in body
source | link

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:

Perfect matchings(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 = \min L$, and go$a$ be an arbitrary element of $L$. Go over all elements $b \in L \setminus a$$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. $$

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:

Perfect matchings($L$):

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

  2. Otherwise, let $a = \min L$, and 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. $$

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

1
source | link

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:

Perfect matchings($L$):

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

  2. Otherwise, let $a = \min L$, and 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. $$