c - 在不生成重复项的情况下查找字符串的所有唯一排列

Question

通过著名的 Steinhaus–Johnson–Trotter 算法查找字符串的所有排列。但是如果字符串中包含
这样的重复字符AABB,
那么可能的唯一组合将是 4!/(2! * 2!) = 6

实现这一点的一种方法是我们可以将其存储在一个数组中，然后删除重复项。

是否有任何更简单的方法来修改 Johnson 算法，以便我们永远不会生成重复的排列。 (以最有效的方式)

Answer 1

首先将字符串转换为一组唯一字符和出现次数，例如香蕉 -> (3, A),(1,B),(2,N)。 (这可以通过对字符串进行排序和对字母进行分组来完成)。然后，对于集合中的每个字母，将该字母少一个字母添加到集合的所有排列之前(注意递归)。继续以“BANANA”为例，我们有: permutations((3,A),(1,B),(2,N)) = A:(permutations((2,A),(1,B),(2 ,N))++ B:(排列((3,A),(2,N))++ N:(排列((3,A),(1,B),(1,N))

这是 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))