Information on Permutations and Combinations of a Multiset

A multiset is like a set, except that repeated elements are allowed. When referring to permutations of a multiset we assume that the elements of the multiset are 0,1,..., t, that the number of occurrences of i is ni and that N = n0 + n1 + ... +nt. Note that if all the ni = 1 then we have an ordinary permutation without repeated elements.

The k-combinations of an n-set are obtained by taking all subsets of the set S = {1,2,...,n} that have k elements. If S is a multiset, then such k-subsets have several applications, notably in statistics, where they arise in permutation tests with repeated data values and as 2 x n contingency tables. Let C(k;n0, n1,..., nt) denote the set of all k subsets of the multiset consisting of ni occurences of i for i = 0..t. Each combination is itself a multiset. For example, C(2;2,1,1) = { {0,0}, {0,1}, {0,2}, {1,2} }. Observe that the k combinations of a multiset where ni = 1 are precisely the k-combinations of a t+1-set.

The k-permutations of an n-set are obtained by taking all of the k-combinations of the same n-set, and then generating all of the permutations of those combinations in every possible way.

The permutations of any multiset can be generated in cool-lex order by a simple rule that produces a prefix-shift Gray code. Suppose s1 s2 ... sn is a permutation, and k is the smallest value such that sk < sk+1. If k+1 = n or sk < sk+2, then the next permutation is obtained by shifting sk+1 into the first position; otherwise, the next permutation is obtained by shifting sk+2 into the first position. (The special case when k is undefined occurs only in the first/last string, and in this case sn is shifted into the first position.) By storing the permutation in a linked list, this rule can be implemented by a loopless algorithm that uses a constant number of additional variables. (See A. Williams, Loopless generation of multiset permutations by prefix-shifts from SODA 2009 for details.)

Relevant Links and References

Programs available: CAT

It was last updated .