Nathaniel: Created page with "{{Function |name=one_factorization |desc=Computes a 1-factorization of a list of objects |upd=November 6, 2014 |rel=perfect_matchings |cat=List of functions#Helper_funct..."

2014-11-07T15:12:40Z

Created page with "{{Function |name=one_factorization |desc=Computes a 1-factorization of a list of objects |upd=November 6, 2014 |rel=perfect_matchings |cat=List of functions#Helper_funct..."

New page

{{Function
|name=one_factorization
|desc=Computes a 1-factorization of a list of objects
|upd=November 6, 2014
|rel=[[perfect_matchings]]
|cat=[[List of functions#Helper_functions|Helper functions]]
|v=0.50
|helper=1}}
<tt>'''one_factorization'''</tt> is a [[List of functions|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 [http://en.wikipedia.org/wiki/Graph_factorization#1-factorization 1-factorization] of the complete graph on $n$ vertices).

Alternatively, this function can be thought of as scheduling a [http://en.wikipedia.org/wiki/Round-robin_tournament 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==
* <tt>FAC = one_factorization(N)</tt>

==Argument descriptions==
* <tt>N</tt>: 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$:
<syntaxhighlight>
>> 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
</syntaxhighlight>

Each row of the output is a single perfect matching (i.e., a way of pairing up the <tt>N</tt> 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).

{{SourceCode|name=one_factorization|helper=1}}

One factorization - Revision history

Nathaniel: Created page with "{{Function |name=one_factorization |desc=Computes a 1-factorization of a list of objects |upd=November 6, 2014 |rel=perfect_matchings |cat=List of functions#Helper_funct..."