没有重复的排列算法？

Question

在我制作的程序中,为一组给定的字母生成字谜,我目前的方法是:

1. 获取所有字母的所有组合
2. 获取每个组合组的排列
3. 按字母顺序对结果排列进行排序
4. 删除重复的条目

我的问题涉及排列的数学.我想知道是否有可能在删除重复条目之后计算存储所有剩余条目所需的数组大小(例如,使用重复字母的数量与排列公式一起使用).

我为我的问题含糊不清道歉,我还在研究更多关于组合和排列的问题.我将尝试详细阐述我的目标,因为我对组合和排列的理解得到了扩展,并且一旦我重新熟悉我的程序(这是我去年夏天的一个业余项目).

Answer 1

如果您有n元素，以及a[0]一个元素的重复项、a[1]另一个元素的重复项，依此类推，直至a[k]，则不同排列的总数（最多重复项）为n!/(a[0]! a[1]! ... a[k]!)。

仅供参考，如果你有兴趣，用番石榴你可以写

Collection<List<Character>> uniquePermutations = 
  Collections2.orderedPermutations(Lists.charactersOf(string));

结果将是字符的独特排列，考虑到重复和所有内容。您甚至可以调用它的.size()方法——或者只是查看它的实现以获取提示。（披露：我为 Guava 做出了贡献。）