2 added 112 characters in body edited Feb 6 at 9:27 Yuval Filmus 200k15193355 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: If $$L = \{a,b\}$$, return $$(a,b)$$. 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$$): If $$L = \{a,b\}$$, return $$(a,b)$$. 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: If $$L = \{a,b\}$$, return $$(a,b)$$. 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 answered Feb 6 at 8:33 Yuval Filmus 200k15193355 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$$): If $$L = \{a,b\}$$, return $$(a,b)$$. 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.$$