是否有一种算法可以列出所有重复有限的排列?如果有现有的 Java 库,那就太好了!
假设我们有 3 个项目{A, B, C}
。我们想要 2 个项目的排列。这将是3 P 2:
{A, B}
{A, C}
{B, A}
{B, C}
{C, A}
{C, B}
但是,如果我们允许最多重复两次。会是什么样子?(我真的不知道。)
我试着想象我们从 set 中得到一个 2 的排列{A, A, B, B, C, C}
。这将是6 P 2 = 30。但我们必须删除那些重复项。我是手工完成的,它是 9。我不知道如何从数学中计算 9。
{A, A}
{A, B}
{A, C}
{B, B}
{B, A}
{B, C}
{C, C}
{C, A}
{C, B}
(实际上3 P 2重复 2 并不是一个很好的例子。这是因为排列中只有 2 个元素。因此,无限重复之间没有区别。重复 2 的4 P 3将是一个更好的例子。但很难列出所有排列。)
一个更好的例子:4 P 3 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, ... }
以及重复限制为 2 的4 P 3组:{A, B, C, D}
{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, ... }
这是一个谈论类似事情的网页。但它似乎需要n P n(选择所有元素)。此外,我仍然需要一种算法来生成和列出排列。
感谢您的帮助!
对于编程实现,其实有一种“不聪明”的做法。
对于 set {A, B, C, D}
,保留一个互补数组int used[0, 0, 0, 0]
,即每个元素的使用次数。每次选择一个元素时增加计数,并将数组的副本向前传递(沿着调用树向下)。然后使用此处启发的递归方法,对其进行更改以允许无限重复(通过不从元素集中删除选定的元素),并if (used[i] <= LIMIT)
在for
.
这是“不聪明”并且不够好,因为我们需要一个互补数组并且每次都需要检查使用的数字。