java - 有限重复置换算法

Question

是否有一种算法可以列出所有重复次数有限的排列？如果有现成的 Java 库就好了!

假设我们有 3 个项目 {A, B, C} .我们想要 2 个项目的排列。它将是₃P₂:

{A, B}
{A, C}
{B, A}
{B, C}
{C, A}
{C, B}

但是如果我们允许最多重复两次。会怎么样？ (我真的不知道。)

我试着想象我们正在从集合 {A, A, B, B, C, C} 中得到 2 的排列.它将是 ₆P₂ = 30。但我们必须删除那些重复项。我自己手工算过，是9。我不知道怎么从数学上算出9。

{A, A}
{A, B}
{A, C}
{B, B}
{B, A}
{B, C}
{C, C}
{C, A}
{C, B}

(事实上 ₃P₂ 重复 2 不是一个很好的例子。这是因为排列中只有 2 个元素。因此, 无限重复之间没有区别。₄P₃ 和重复 2 是一个更好的例子。但是很难列出所有排列。 )

一个更好的例子来说明:₄P₃ of set {A, B, C, D} :

{A, B, C}
{A, B, D}
{A, C, B}
{A, C, D}
{A, D, B}
{A, D, C}
... repeat for permutations starting from {B, ... }
... repeat for permutations starting from {C, ... }
... repeat for permutations starting from {D, ... }

和 ₄P₃ 的集合 {A, B, C, D}重复次数限制为 2:

{A, A, B}
{A, A, C}
{A, A, D}

{A, B, A}
{A, B, B}
{A, B, C}
{A, B, D}

{A, C, A}
{A, C, B}
{A, C, C}
{A, C, D}

{A, D, A}
{A, D, B}
{A, D, C}
{A, D, D}

... repeat for permutations starting from {B, ... }
... repeat for permutations starting from {C, ... }
... repeat for permutations starting from {D, ... }

Here是一个谈论类似事情的网页。但它似乎需要 _nP_n (选择所有元素)。此外，我还需要一种算法来生成和列出排列。

感谢您的帮助!

---

对于编程实现，其实有一种“不聪明”的做法。

对于集合 {A, B, C, D} , 保留互补数组 int used[0, 0, 0, 0] ，这是每个元素被使用的次数。每次选择一个元素时增加计数，并向前传递数组的副本(向下调用树)。然后用递归方法启发here ，改变它以允许无限重复(通过不从元素集中删除选定的一个)，并添加一个 if (used[i] <= LIMIT) for 之后的检查语句.

这“不聪明”并且不够好，因为我们需要一个互补数组并且每次都需要检查使用的数字。

Answer 1

在生成集合的所有可能分区之前，我已经遇到过这个问题。这与您尝试执行的操作本质上是相同的概念。 (给定大小的所有组合与该大小的分区集相同)我找到了this这篇论文提供了一种非常快速的非递归算法来生成这些组合而无需任何重复以及 c++ 实现。