Perfect matchings
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 here to view this function's source code on github.