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 n_{i} and that N = n_{0} + n_{1} + ... +n_{t}. Note that if all the n_{i} = 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;n_{0}, n_{1},..., n_{t}) denote the set of all k subsets of the multiset consisting of n_{i} 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 n_{i} = 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 s_{1} s_{2} ... s_{n} is a permutation, and k is the smallest value such that s_{k} < s_{k+1}. If k+1 = n or s_{k} < s_{k+2}, then the next permutation is obtained by shifting s_{k+1} into the first position; otherwise, the next permutation is obtained by shifting s_{k+2} into the first position. (The special case when k is undefined occurs only in the first/last string, and in this case s_{n} 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.)