I am currently working on a project where I have to perform a computation over all possible permutations of a multiset $S$. In my setting, each multiset is a list of small positive integers such as $S = [1, 1, 3, 4]$ with between 2 to 10 elements and at least 1 duplicate.
I am wondering if there is an algorithm to generate distinct permutations of S by swapping two elements at a time? I am open to any algorithm, though ideally I am hoping to find an iterative procedure.
Example: Given $S = [1,1,3,4]$, the algorithm would output $12 = 4!/(2!1!1!)$ distinct permutations $P_1, P_2,\ldots, P_{12}.$ The permutations would be distinct in the sense that $P_t \neq P_{t'}$ for all $t,t'$. Given a permutation $P_t$ where $t < 12$, the algorithm would produce the next permutation $P_{t+1}$ would be by swapping the elements of $P_t$ at locations $i$ and $j$. Thus:
$\begin{align} P_{t+1}[i] &= P_t[j]\\ P_{t+1}[j] &= P_t[i]\\ P_{t+1}[k] &= P_t[k] \quad \textrm{for}~k \neq i,j \end{align} $
Note that we do note need for there to exist a "swap" that would transform the last permutation $P_{12}$ into the first permutation $P_1$. In this sense, the problem is easier because the permutations would not need to form a Hamiltonian path.
I also did a bit of background research and discovered the following facts that might help:
- It seems as if there is a result that shows that it is impossible to generate the permutations of a multiset through adjacent swaps (see e.g., p.2 of this paper). However, I am not sure if this result holds when we are allowed to perform non-adjacent swaps.
- The FXT library has several implementations of algorithms for multiset permutation. This algorithm seems to fit the bill (see code and sample output). I am hesitant about using it since I have not seen it mentioned in a paper or textbook and I'm not familiar with C++ syntax. If someone could confirm that it works and explain it, that would also be an acceptable solution.
