```help mata mm_subset()
-------------------------------------------------------------------------------

Title

mm_subset() -- Obtain subsets, compositions, and partitions

Syntax

info = mm_subsetsetup(n [, k])

real colvector  mm_subset(info)

real matrix  mm_subsets(n [, k])

info = mm_compositionsetup(n [, k, alt])

real colvector  mm_composition(info)

real matrix  mm_compositions(n [, k, alt])

real scalar  mm_ncompositions(n [, k])

info = mm_partitionsetup(n [, k, pad, alt])

real colvector  mm_partition(info)

real matrix  mm_partitions(n [, k, alt])

real scalar  mm_npartitions(n [, k])

real colvector  mm_rsubset(n [, k])

real colvector  mm_rcomposition(n [, k])

where

n:  real scalar n

k:  real scalar k

pad:  real scalar indicating that the partitions be padded with
0s to have length k

alt:  real scalar indicating that the alternative algorithm be
used

and where info should be declared transmorphic.

Description

mm_subset(info), where info is set by mm_subsetsetup(), returns all
k-subsets (combinations) of n elements, one at a time in lexicographic
order. If k is omitted or if k==., the n-subset is returned. Hint: The
total number of subsets can be computed as comb(n, k). Algorithm 5.8 from
Reingold et al. (1977) is used to generate the subsets.

mm_subsets() is a wrapper for mm_subset() and returns a matrix containing
all subsets.

mm_composition(info), where info is set by mm_compositionsetup(), returns
all k-part compositions of a positive integer n, one at a time. If k is
omitted or if k==., then the n-part compositions of n are returned. The
default algorithm uses a direct approach and returns the compositions in
anti-lexicographic order. The alternative algorithm, which is applied if
alt!=0 is specified, generates the compositions indirectly (in
lexicographic order) by using the mm_subset() function (as suggested by
Reingold et al. 1977, p. 190-191). The default algorithm is about 1/3
faster than the alternative algorithm.

mm_compositions() is a wrapper for mm_composition() and returns a matrix
containing all compositions.

mm_ncompositions() returns the total number of k-part compositions of n,
which is equal to comb(n+k-1,k-1).

mm_partition(info), where info is set by mm_partitionsetup(), returns all
partitions with k or fewer addends of a positive integer n, one at a
time. If k is omitted or if k==., then the partitions with n or fewer
addends are returned. The default algorithm is based on Algorithm ZS1 by
Zoghbi and Stojmenovic (1998; with modifications to allow the k
parameter) and returns the partitions in anti-lexicographic order.  The
alternative algorithm, which is applied if alt!=0 is specified, is based
on Algorithm 5.12 in Reingold et al. (1977) and returns the partitions in
lexicographic order. The default algorithm is much faster than the
alternative algorithm, especially if k is low compared to n.

mm_partitions() is a wrapper for mm_partition() and returns a matrix
containing all partitions.

mm_npartitions() returns the total number of partitions with k or fewer
addends of a positive integer n (based on algorithms given on
modifications to allow the k parameter). mm_npartitions() may be slow if
k<n and n is large (> 1000, say).

mm_rsubset() returns a random k-subset of n elements. mm_rcomposition()
returns a random k-part compositions of n (based on ideas presented in
Reingold et al. 1977, p. 189).

The procedure to cycle through all combinations, compositions, or
partitions is to initialize info using the setup function and then
repeatedly call the combinatorial function until it returns J(0,1,.). For
example:

info = mm_subsetsetup(n, k)
while ((set=mm_subset(info)) != J(0,1,.)) {
... set ...
}

Remarks

Examples:

: comb(4,3)
4

: mm_subsets(4,3)
1   2   3   4
+-----------------+
1 |  1   1   1   2  |
2 |  2   2   3   3  |
3 |  3   4   4   4  |
+-----------------+

: mm_ncompositions(4,3)
15

: mm_compositions(4,3)
1    2    3    4    5    6    7    8    9   10
+---------------------------------------------------
1 |   4    3    3    2    2    2    1    1    1    1
2 |   0    1    0    2    1    0    3    2    1    0
3 |   0    0    1    0    1    2    0    1    2    3
+---------------------------------------------------
11   12   13   14   15
--------------------------+
1     0    0    0    0    0  |
2     4    3    2    1    0  |
3     0    1    2    3    4  |
--------------------------+

: mm_npartitions(4,3)
4

: mm_partitions(4,3)
1   2   3   4
+-----------------+
1 |  4   3   2   2  |
2 |  0   1   2   1  |
3 |  0   0   0   1  |
+-----------------+

See the source code of mm_mgof() for some applications.

Diagnostics

mm_subset(), mm_composition(), and mm_permutation() return J(0,1,.) when
there are no more combinations, compositions, or permutations.

Source code

mm_subset.mata

References

Reingold, E. M., J. Nievergelt, N. Deo (1977). Combinatorial Algorithms:
Theory and Practice. Englewood Cliffs, NJ: Prentice-Hall.
Zohgbi, A., I. Stojmenovic (1998). Fast Algorithms for Generating
Partitions. International Journal of Computer Mathematics 70:
319-332.

Also see

Online:  help for [M-5] cvpermute(), [M-4] statistical, mm_mgof(),
moremata
```