c - Finding all the unique permutations of a string without generating duplicates

Question

Finding all the permutations of a string is by a well known Steinhaus–Johnson–Trotter algorithm. But if the string contains the repeated characters such as
AABB,
then the possible unique combinations will be 4!/(2! * 2!) = 6

One way of achieving this is that we can store it in an array or so and then remove the duplicates.

Is there any simpler way to modify the Johnson algorithm, so that we never generate the duplicated permutations. (In the most efficient way)

Answer 1

First convert the string to a set of unique characters and occurrence numbers e.g. BANANA -> (3, A),(1,B),(2,N). (This could be done by sorting the string and grouping letters). Then, for each letter in the set, prepend that letter to all permutations of the set with one less of that letter (note the recursion). Continuing the "BANANA" example, we have: permutations((3,A),(1,B),(2,N)) = A:(permutations((2,A),(1,B),(2,N)) ++ B:(permutations((3,A),(2,N)) ++ N:(permutations((3,A),(1,B),(1,N))

Here is a working implementation in Haskell:

circularPermutations::[a]->[[a]]
circularPermutations xs = helper [] xs []
                          where helper acc [] _ = acc
                                helper acc (x:xs) ys =
                                  helper (((x:xs) ++ ys):acc) xs (ys ++ [x])

nrPermutations::[(Int, a)]->[[a]]
nrPermutations x | length x == 1 = [take (fst (head x)) (repeat (snd (head x)))]
nrPermutations xs = concat (map helper (circularPermutations xs))
  where helper ((1,x):xs) = map ((:) x)(nrPermutations xs)
        helper ((n,x):xs) = map ((:) x)(nrPermutations ((n - 1, x):xs))