# Is there an algorithm to generate all permutations of a multiset through swaps?

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:

1. 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.
2. 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.
• The FXT library sounds like it might be worth another look. Whether you've seen it mentioned in a paper or textbook doesn't seem well correlated to the quality of the library; in my experience papers and textbooks are more likely to mention algorithms than implementations. If FXT does what you want, the language it is implemented in might be secondary. – D.W. Jan 6 at 22:47
• – D.W. Jan 6 at 22:53