One factorization

From QETLAB
Jump to: navigation, search
one_factorization
Computes a 1-factorization of a list of objects

Other toolboxes required none
Related functions perfect_matchings
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.

one_factorization is a function that returns a 1-factorization of a given list of objects. That is, for a list of $n$ objects, it returns $n-1$ ways of pairing up all of the objects such that each pair of objects occurs exactly once (and thus is essentially a 1-factorization of the complete graph on $n$ vertices).

Alternatively, this function can be thought of as scheduling a round-robin tournament: given an even number $n$ of players, it shows how each player can play against every other player by pairs of players playing $n/2$ games concurrently $n-1$ times (which is optimal).

Syntax

  • FAC = one_factorization(N)

Argument descriptions

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

Examples

A 1-factorization of six objects

The following code generates a 1-factorization of the numbers $1,2,3,4,5,6$:

>> one_factorization(6)
 
ans =
 
     1     6     5     2     4     3
     2     6     1     3     5     4
     3     6     2     4     1     5
     4     6     3     5     2     1
     5     6     4     1     3     2

Each row of the output is a single perfect matching (i.e., a way of pairing up the N objects), which are read "naively" left-to-right. For example, the first row of the output above indicates the following pairing: $\{\{1,6\},\{5,2\},\{4,3\}\}$. The other rows are similar, and each pair occurs exactly once in the entire matrix (e.g., the pair $\{1,3\}$ occurs only in the 2nd row).

Source code

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

  1. %%  ONE_FACTORIZATION    Computes a 1-factorization of a list of 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. %   FAC = one_factorization(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. The perfect matchings that are
  12. %   returned have the property that every pair of objects is included in
  13. %   exactly one of the perfect matchings (i.e., these perfect matchings
  14. %   together make up a 1-factorization of the complete graph).
  15. %
  16. %   URL: http://www.qetlab.com/one_factorization
  17.  
  18. %   requires: nothing
  19. %   author: Nathaniel Johnston (nathaniel@njohnston.ca)
  20. %   package: QETLAB
  21. %   last updated: November 6, 2014
  22.  
  23. function fac = one_factorization(n)
  24.  
  25. if(length(n) == 1)
  26.     n = 1:n;
  27. end
  28. sz = length(n);
  29.  
  30. % If we were given an odd number of objects, no 1-factorization exists.
  31. if(mod(sz,2) == 1)
  32.     error('one_factorization:DoesNotExist','There is no 1-factorization of an odd number of objects.');
  33. end
  34.  
  35. fac = zeros(sz-1,sz);
  36. for j=1:sz-1
  37.     fac(j,[1,2]) = [n(j),n(sz)];
  38.     for k=2:(sz/2)
  39.         fac(j,[2*k-1,2*k]) = [n(mod(j-(k-1)-1,sz-1)+1),n(mod(j+(k-1)-1,sz-1)+1)];
  40.     end
  41. end