# Is there a specific search paradigm for finding pairs in a set?

I'm dealing with a very common problem in computer programming that involves, for example 4 people to be divided into 2 pairs. Mathematically, this is just a permutations problem, and the number of possibilities would be 4!/(2! * 2^2) = 3.

In computer programming, when searching for these specific solutions, a programmer would just recurse through the possible solutions. For example --

int solve(void) {
int i, count = 0;
for (i = 0; i < n; i++) {
if (partners[i] == -1) {
break;
}
}

// if all the pairs are matched with each other
if (i == n) {
return check() ? 1 : 0;
}

for (int j = i + 1; j < n; j++) {
if (partners[j] == -1) {
partners[i] = j;
partners[j] = i;

// recurse back through to find all possible sets of pairs with this configuration
count += solve();
partners[i] = partners[j] = -1;
}
}
return count;
}


Now, what I found interesting was that when you draw a permutation tree diagram, you see that the unique solutions for this problem arise naturally in this pattern: Permutation Tree. This pattern goes on as the number of people increases. Taking all that into account, my question is, is this simple recursive function a unique search paradigm (like BFS or DFS) that models the behavior/pattern seen in the tree? If not, could an algorithm be designed that models that pattern?

I'm a high school student, and I'm comfortable with basic and intermediate algorithm design concepts, but I'm still learning, so if you could, please explain your answer in more depth than usual.

• You are enumerating all perfect matchings of a complete graph. These are counted by a double factorial. There are probably many ways of enumerating all perfect matchings. – Yuval Filmus Jan 3 '19 at 21:19
• ok, that helps a bit, how would you identify the time complexity of the function? It's clearly exponential, an input size of n = 2, 4, 6, 8, 10, 12 would have y = 2, 7, 36, 253, 2278, 25059 operations respectively, can it be fit into any specific function? – user2300851 Jan 3 '19 at 22:27
• The asymptotics should be very similar to the double factorial. If you’re lucky, you’ll find your sequence on the OEIS. – Yuval Filmus Jan 3 '19 at 22:30
• Yes you're right! I found it on OEIS, it is the row sums of a double factorial triangle. Thanks so much! – user2300851 Jan 3 '19 at 22:42
• You can self-answer your question and accept it. – Evil Jan 4 '19 at 3:00