Perfect matchings

From QETLAB
Jump to: navigation, search
perfect_matchings
Gives all perfect matchings of N objects

Other toolboxes required none
Related functions BrauerStates
one_factorization
Function category Helper functions
This is a helper function that only exists to aid other functions in QETLAB. If you are an end-user of QETLAB, you likely will never have a reason to use this function.

perfect_matchings is a function that returns all perfect matchings of a given list of objects. That is, it returns all ways of grouping an even number of objects into pairs.

Syntax

  • PM = perfect_matchings(N)

Argument descriptions

  • N: Either an even integer, indicating that you would like all perfect matchings of the integers $1, 2, \ldots, N$, or a vector containing an even number of distinct entries, indicating that you would like all perfect matchings of those entries.

Examples

Perfect matchings of four objects

The following code generates all perfect matchings of the numbers $1,2,3,4$:

>> perfect_matchings(4)
 
ans =
 
     1     2     3     4
     1     3     2     4
     1     4     3     2

The perfect matchings are read "naively" left-to-right. For example, the first row of the output above indicates that one valid perfect matching is $\{\{1,2\},\{3,4\}\}$. The second row says that another perfect matching is $\{\{1,3\},\{2,4\}\}$. Finally, the third row says that the third (and last) perfect matching is $\{\{1,4\},\{2,3\}\}$.

Notes

If $N = 2k$ then there are exactly $(2k)!/(k!\cdot 2^k)$ perfect matchings of $N$ objects. If $N$ is odd, there are no perfect matchings (and thus PM will have zero rows).

Source code

Click on "expand" to the right to view the MATLAB source code for this function.

  1. %%  PERFECT_MATCHINGS    Gives all perfect matchings of N objects
  2. %   This function has one required argument:
  3. %     N: either an even natural number (the number of objects to be
  4. %        matched) or a vector containing an even number of distinct objects
  5. %        to be matched
  6. %
  7. %   PM = perfect_matchings(N) is a matrix with each row corresponding to a
  8. %   perfect matching of N objects (or, if N is a vector, each row of PM is
  9. %   a pefect matching of the entries of N). Each perfect matching is read
  10. %   "naively": for each j, PM(j,1) is matched with PM(j,2), PM(j,3) is
  11. %   matched with PM(j,4), and so on.
  12. %
  13. %   URL: http://www.qetlab.com/perfect_matchings
  14.  
  15. %   requires: nothing
  16. %   author: Nathaniel Johnston (nathaniel@njohnston.ca)
  17. %   package: QETLAB
  18. %   last updated: November 6, 2014
  19.  
  20. function pm = perfect_matchings(n)
  21.  
  22. if(length(n) == 1)
  23.     n = 1:n;
  24. end
  25. sz = length(n);
  26.  
  27. % Base case, n = 2: only one perfect matching.
  28. if(sz == 2)
  29.     pm = n;
  30.     return;
  31.  
  32. % There are no perfect matchings of an odd number of objects.
  33. elseif(mod(sz,2) == 1)
  34.     pm = zeros(0,sz);
  35.     return;
  36. end
  37.  
  38. % Recursive step: build perfect matchings from smaller ones.
  39.  
  40. % Only do the recursive step once instead of n-1 times: we will then tweak
  41. % the output n-1 times.
  42. lower_fac = perfect_matchings(n(3:end));
  43. lfac_size = size(lower_fac,1);
  44. pm = zeros(0,sz);
  45.  
  46. % Now build the perfect matchings we actually want.
  47. for j = 2:sz
  48.     tlower_fac = lower_fac;
  49.     tlower_fac(tlower_fac==n(j)) = n(2);
  50.     pm = [pm;[ones(lfac_size,1)*[n(1),n(j)],tlower_fac]];
  51. end