java - 没有重复的排列算法？

Question

在我正在为给定的一组字母生成字谜的程序中，我目前的方法是：

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

我的问题与排列的数学有关。我想知道是否有可能在删除重复条目后完全计算存储所有剩余条目所需的数组大小（例如，使用重复字母的数量与排列公式或其他东西结合使用）。

对于我的问题含糊不清，我深表歉意，我仍在研究更多关于组合和排列的信息。随着我对组合和排列的理解的扩展，我将尝试详细说明我的目标，一旦我重新熟悉了我的程序（这是我去年夏天的一个业余项目）。

Answer 1

如果您有n元素、a[0]一个元素的a[1]重复项、另一个元素的重复项，等等，直到a[k]，那么不同排列的总数（最多重复项）为n!/(a[0]! a[1]! ... a[k]!)。

仅供参考，如果您有兴趣，可以使用Guava编写

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

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

Answer 2

生成所有排列确实是个坏主意。例如，“溢出”一词有 40320 个排列。因此，随着字长的增加，内存消耗会变得非常高。

我相信你试图解决的问题可以简化为找出一个词是否是另一个词的字谜。

然后你可以通过计算每个字母出现的次数（它将是一个 26 元组）并将这些元组相互比较来解决它。