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 做出了贡献。)