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.
  • $\begingroup$ 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. $\endgroup$ – D.W. Jan 6 '20 at 22:47
  • $\begingroup$ Related: mathoverflow.net/q/279844/37212, en.wikipedia.org/wiki/Heap%27s_algorithm $\endgroup$ – D.W. Jan 6 '20 at 22:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.