有限重复排列算法

Question

是否有算法以有限的重复列出所有排列？如果有一个现有的Java库,那就太好了!

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

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

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

我尝试成像,我们从集合中得到2的排列{A, A, B, B, C, C}.它将是₆ P ₂ = 30.但是我们必须拿走那些重复的东西.我已经手动完成它,它是9.我不知道如何从数学计算9.

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

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

一个更好的例子示例:₄ P ₃的集合{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, ... }

这是一个谈论类似事情的网页.但它似乎需要_n P _n(选择所有元素).此外,我仍然需要一个算法来生成和列出排列.

谢谢你的帮助!

---

对于编程实现,实际上存在"不智能"的方法.

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

这是"不聪明"而且不够好,因为我们需要一个互补的数组,并且每次都需要检查使用过的数字.

Answer 1

我之前在生成集合的所有可能分区时遇到过这个问题。这本质上与您想要做的概念相同。（给定大小的所有组合与该大小的分区集相同）我发现这篇论文提供了一种非常快速的非递归算法来生成这些组合，无需任何重复以及 C++ 实现。