是否有一种算法可以列出重复次数有限的所有排列？如果有一个现有的Java库，那就太好了!
假设我们有3个项目{A, B, C}。我们想要2个项目的排列。它将是3P2:
{A, B}
{A, C}
{B, A}
{B, C}
{C, A}
{C, B}
但是，如果我们允许最大重复两次。感觉如何？ (我真的不知道。)
我尝试想象一下我们从
{A, A, B, B, C, C}集合中得到了2的排列。它将是6P2 =30。但是我们必须删除那些重复项。我已经手工完成了，现在是9。我不知道如何从数学中计算9。{A, A}
{A, B}
{A, C}
{B, B}
{B, A}
{B, C}
{C, C}
{C, A}
{C, B}
(实际上，重复2的3P2并不是一个很好的例子。这是因为排列中只有2个元素。因此，无限重复之间没有区别。重复2的4P3将是一个更好的例子。但是列出所有排列是很困难的。)
一个更好的例子:set
{A, B, C, D}的4P3:{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, ... }
并设置了
{A, B, C, D}的4P3，其重复限制为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是一个谈论类似内容的网页。但似乎需要nPn(选择所有元素)。另外，我仍然需要一种算法来生成并列出排列。
感谢您的帮助!
对于编程实现，实际上有一种“不明智”的方法。
对于set
{A, B, C, D}，请保留一个互补数组int used[0, 0, 0, 0]，这是每个元素的使用次数。每次选择元素时增加计数，然后向前(在调用树下方)传递数组的副本。然后，使用启发式here的递归方法，对其进行更改以允许无限重复(通过不从元素集中删除选定的重复项)，并在if (used[i] <= LIMIT)之后添加for检查语句。这是“不明智的”并且还不够好，因为我们需要一个互补的数组，并且需要每次检查使用的数字。
最佳答案
在生成集合的所有可能分区之前，我已经遇到了这个问题。这实际上与您要尝试执行的概念相同。 (给定大小的所有组合都与该大小的分区集相同)我发现this论文提供了一种非常快速的非递归算法来生成这些组合，而无需任何重复以及c++实现。