Generate permutations of a multiset

Generate all permutations of a multiset. Provide the multiset by specifying its frequency sequence, e.g. "1 1 3 2" for the multiset $\{1,2,3,3,3,4,4\}$.
Frequency sequence (max. 20)
Algorithm
Output format
Output  numbering graphics

Object info

A multiset is a set where some elements may appear multiple times. For simplicity, we always consider the ground set $\{1,2,\ldots,n\}$. The number of times that each element appears in the multiset is counted by the frequency sequence $f_1,f_2,\ldots,f_n$, i.e., $f_i$ counts the number of occurences of the element $i$. Multiset permutations generalize many other combinatorial objects. Specifically, a multiset permutation with $f_1=f_2=\cdots=f_n=1$ is an ordinary permutation, and a multiset permutation with $n=2$ is a combination, i.e., it can be interpreted as the characteristic vector of an $f_1$-element subset of an $(f_1+f_2)$-element ground set.

The first three algorithms running on this page are part of Jörg Arndt's FXT library. The iterative algorithm for lexicographic ordering is explained in Jörg Arndt's FXT library [Section 13.2.2, Arn10]. The minimal-change algorithm follows a Steinhaus-Johnson-Trotter adjacent transposition strategy by Fred Lunnon. Lunnon sent the algorithm to Jörg Arndt as a personal communication, and it appears in Arndt's book [Section 13.2.4, Arn10]. The prefix rotation algorithm uses a multiset generalization of cool-lex order by Williams [Wil09]. The implementation is currently from Arndt's book [Section 13.2.3, Arn10]. Cool-lex order can also be filtered by the aperiodic prefixes of its necklaces, and the result is a shorthand universal cycle for the multiset permutations. When these multiset permutations are listed the order uses only prefix rotations of length $n-1$ and $n$. This result is explained in Williams' PhD thesis [Section 13.2.3, Wil09b].

Enumeration (OEIS)

The number of multiset permutations with frequency sequence $f_1,f_2,\ldots f_n$ is given by the multinomial coefficients $\binom{s}{f_1,f_2,\ldots,f_n}$ with $s:=f_1+f_2+\cdots +f_n$.

Download source code

[Zipped C++ source code (GNU GPL)]
[Link to Jörg Arndt's FXT library (GNU GPL)]

References