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

Title

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

Syntax

info=mm_subsetsetup(n[,k])

real colvectormm_subset(info)

real matrixmm_subsets(n[,k])

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

real colvectormm_composition(info)

real matrixmm_compositions(n[,k,alt])

real scalarmm_ncompositions(n[,k])

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

real colvectormm_partition(info)

real matrixmm_partitions(n[,k,alt])

real scalarmm_npartitions(n[,k])

real colvectormm_rsubset(n[,k])

real colvectormm_rcomposition(n[,k])

where

n:real scalar n

k:real scalar k

pad:real scalarindicating that the partitions be padded with 0s to have lengthk

alt:real scalarindicating that the alternative algorithm be used

and where

infoshould be declaredtransmorphic.

Description

mm_subset(info), whereinfois set bymm_subsetsetup(), returns allk-subsets (combinations) ofnelements, one at a time in lexicographic order. Ifkis omitted or ifk==., then-subset is returned. Hint: The total number of subsets can be computed ascomb(n,k). Algorithm 5.8 from Reingold et al. (1977) is used to generate the subsets.

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

mm_composition(info), whereinfois set bymm_compositionsetup(), returns allk-part compositions of a positive integern, one at a time. Ifkis omitted or ifk==., then then-part compositions ofnare returned. The default algorithm uses a direct approach and returns the compositions in anti-lexicographic order. The alternative algorithm, which is applied ifalt!=0 is specified, generates the compositions indirectly (in lexicographic order) by using themm_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 formm_composition()and returns a matrix containing all compositions.

mm_ncompositions()returns the total number ofk-part compositions ofn, which is equal tocomb(n+k-1,k-1).

mm_partition(info), whereinfois set bymm_partitionsetup(), returns all partitions withkor fewer addends of a positive integern, one at a time. Ifkis omitted or ifk==., then the partitions withnor fewer addends are returned. The default algorithm is based on Algorithm ZS1 by Zoghbi and Stojmenovic (1998; with modifications to allow thekparameter) and returns the partitions in anti-lexicographic order. The alternative algorithm, which is applied ifalt!=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 ifkis low compared ton.

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

mm_npartitions()returns the total number of partitions withkor fewer addends of a positive integern(based on algorithms given on http://home.att.net/~numericana/answer/numbers.htm#partitions, with modifications to allow thekparameter).mm_npartitions()may be slow ifk<nandnis large (> 1000, say).

mm_rsubset()returns a randomk-subset ofnelements.mm_rcomposition()returns a randomk-part compositions ofn(based on ideas presented in Reingold et al. 1977, p. 189).The procedure to cycle through all combinations, compositions, or partitions is to initialize

infousing the setup function and then repeatedly call the combinatorial function until it returnsJ(0,1,.). For example:

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

RemarksExamples:

: 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(), andmm_permutation()return J(0,1,.) when there are no more combinations, compositions, or permutations.

Source codemm_subset.mata

ReferencesReingold, 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 seeOnline: help for

[M-5] cvpermute(),[M-4] statistical,mm_mgof(),moremata