0
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Yuval Filmus Jan 3 at 21:19
  • $\begingroup$ 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? $\endgroup$ – user2300851 Jan 3 at 22:27
  • $\begingroup$ The asymptotics should be very similar to the double factorial. If you’re lucky, you’ll find your sequence on the OEIS. $\endgroup$ – Yuval Filmus Jan 3 at 22:30
  • $\begingroup$ Yes you're right! I found it on OEIS, it is the row sums of a double factorial triangle. Thanks so much! $\endgroup$ – user2300851 Jan 3 at 22:42
  • $\begingroup$ You can self-answer your question and accept it. $\endgroup$ – Evil Jan 4 at 3:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.