This is something that I thought of on my own, though I am sure that I am not the first to think of it.

The easiest way to explain this is by using an example. Suppose we want to find the unique permutations of the letters in "beet". The first step of the algorithm is to create a corresponding permutation of the indices into the text: $\{1,2,3,4\}$. Generate all permutations on the numbers using Johnson-Trotter, which works with transpositions of adjacent elements. Consider the letter permutation "eteb", whose index representation would be either $\{2,4,3,1\}$ or $\{3,4,2,1\}$. The algorithm chooses the first case, because it only returns a text permutation when the indices for each letter are in ascending order, satisfied by the first case, since the indices of "$e", 2$ and $3$, are in ascending order.

Because we are only working with transpositions of adjacent elements, it is easy to tell when the indices for each letter are in ascending order. The order only changes when two identical letters are about to be transposed. In such cases, a disorder counter, initialized to $0$, will be incremented by $1$ if the higher index is going to be placed before the lower one, and will be decremented by $1$ in the other case. Only return a permutation of the letters if the disorder counter is $0$.

  • $\begingroup$ To summarize, you rely on a method (any method) for permuting unique indices, and then check that each subset of indices whose targets are equal is in ascending order. It is not clear what you are asking about this approach, which perhaps explains why no one responded in the first few hours. $\endgroup$ – hardmath May 9 '16 at 22:45
  • $\begingroup$ @hardmath, I just wanted to know if this is a reasonable algorithm for generating unique permutations in terms of complexity and efficiency. $\endgroup$ – user1153980 May 10 '16 at 1:29

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.