Algorithm of Permutation with Limited Repetition

Question

Is there an algorithm to list out all the permutations with a limited repetition? If there is an existing Java library, it would be so nice!

Let's say we have 3 items {A, B, C}. We want a permutation of 2 items. It would be ₃P₂:

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

But if we allow a maximum repetition of twice. How it would be like? (i don't really know.)

I try to imaging we are getting a permutation of 2 from the set {A, A, B, B, C, C}. It would be ₆P₂ = 30. But we have to take away those duplicates. I have done it by hand and it is 9. I don't know how to calculate 9 from maths.

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

(In fact ₃P₂ with a repetition of 2 is not a good example. It is because there are only 2 elements in the permutations. Therefore, there are no differences between an unlimited repetition. ₄P₃ with a repetition of 2 would be a nicer example. But it would be tough to list out all the permutations.)

A better example for illustration: ₄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, ... }

And ₄P₃ of set {A, B, C, D} with a repetition limit of 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 is a webpage talking about similar thing. But it seems it requires _nP_n (selecting all the elements). Also, i still need an algorithm to generate and list out the permutations.

Thanks for your helps!

---

For programming implementation, in fact there is a "not smart" approach.

For set {A, B, C, D}, keep a complementary array int used[0, 0, 0, 0], which are the numbers of times each element is used. Increment the count every time an element is chosen, and pass a copy of the array forward (down the call tree). Then with the recursive approach inspired here, alter it to allow unlimited repetition (by not deleting the selected one from the element set), and add an if (used[i] <= LIMIT) checking statement after for.

This is "not smart" and not good enough because we need a complementary array and require checking the used number every time.

Answer 1

I have come into this problem before with generating all the possible partitions of a set. This is essentially the same concept as what you are trying to do. (All combinations of a given size is the same as the set of partitions of that size) I found this paper that gave a very fast non recursive algorithm to generate these combinations without any repetition along with a c++ implementation.