Loopless generation of multiset permutations using a constant number of variables by prefix shifts
Aaron Williams · 2009
This paper answers the following mathematical question: Can multiset permutations be ordered so that each permutation is a prefix shift of the previous permutation? Previously, the answer was known for the permutations of any set, and the permutations of any multiset whose corresponding set contains only two elements. This paper also answers the following algorithmic question: Can multiset permutations be generated by a loopless algorithm that uses sublinear additional storage? Previously, the best loopless algorithm used a linear amount of additional storage. The answers to these questions are both yes.