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
    http://home.att.net/~numericana/answer/numbers.htm#partitions, with
    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