# Algorithm of Permutation with Limited Repetition

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 3P2:

``````{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 6P2 = 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 3P2 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. 4P3 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: 4P3 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 4P3 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 nPn (selecting all the elements). Also, i still need an algorithm to generate and list out the permutations.

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.

-
Wouldn't generating the permutations of `{A, B, C}` (of any length) allowing a single repetition of each element be the same as generating the permutations of `{A, A, B, B, C, C}` of the same length? –  beaker Jul 12 '13 at 21:01
For length = 3, if elements of `{A, A, B, B, C, C}` are distinct, i.e. `A != A`, it would be P(6, 3), and having duplicated `{A, A, B}` and `{A, A, B}`, which is unwanted. –  midnite Jul 12 '13 at 21:29
Ah, good point. –  beaker Jul 12 '13 at 21:33
Technically speaking, a set cannot allow repetition –  mor Jul 12 '13 at 21:43
@ricard.m.o., Hmm... do you mean nPr / permutation cannot deal with repeated element? If so, we may have to think in another way. –  midnite Jul 12 '13 at 21:51

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.

-

See this paper that finds a theoretical formula for the number of answers. The paper information is: "Permutations with limited repetitions" by Roberto Frucht from Journal of Combinatorial Theory with doi of 10.1016/S0021-9800(66)80025-X

-

Well, this is a little late, but I have a Java Combinatorics library up on GitHub that will do this. Here is the basic usage:

Include the dependency in your project:

``````<dependency>
<groupId>com.xiantrimble.combinatorics</groupId>
<artifactId>combinatorics</artifactId>
<version>0.2.0</version>
<dependency>
``````

Then iterate the permutations by getting a virtual collection from the combinatoric factory:

``````import com.xiantrimble.combinatorics.CombinatoricFactory;
import com.xiantrimble.combinatorics.CombinatoricFactoryImpl;
import com.xiantrimble.combinatorics.Combinatoric;
...
int k = 6;
int[] domain = {1,1,1,1,2,2,2,3,3,4};
// create a factory.
CombinatoricFactory factory = new CombinatoricFactoryImpl();
Combinatoric<Integer> permutations = factory.createPermutations(k,  domain);

for( Integer[] permutation : permutations ) {
System.out.println(Arrays.toString(permutation));
}
``````

The code does not do a dictionary order, but is instead geared toward trying to minimize the change between consecutive elements, so keep that in mind. Also, there are some improvements in the 0.3.0-SNAPSHOT version, which is available on Sonatype's snapshot repository.

-
The text passage primarily discusses the problem of generating permutations with limited repetition, providing examples and discussing potential approaches and algorithms. It also mentions a Java library that can be used to solve this problem.
no_question

the passage does not contain a direct mathematical question that requires an answer. it is more of a discussion or explanation of a problem and potential solutions. while it mentions calculations and permutations, it does not ask a specific question that needs to be answered within the text.
Given a text passage, determine:
    1. If it contains a mathematical question (including word problems or calculations)
    2. If an answer to that mathematical question is provided in the text

First, describe the content structure you found in 1-2 sentences.

Then provide your analysis in the following format:
TYPE: <one of the following values>
- NO_QUESTION
- SINGLE_QUESTION
- SINGLE_QUESTION_WITH_ANSWER
- MULTIPLE_QUESTIONS
- MULTIPLE_QUESTIONS_WITH_ANSWERS
system
# Algorithm of Permutation with Limited Repetition

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 3P2:

``````{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 6P2 = 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 3P2 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. 4P3 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: 4P3 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 4P3 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 nPn (selecting all the elements). Also, i still need an algorithm to generate and list out the permutations.

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.

-
Wouldn't generating the permutations of `{A, B, C}` (of any length) allowing a single repetition of each element be the same as generating the permutations of `{A, A, B, B, C, C}` of the same length? –  beaker Jul 12 '13 at 21:01
For length = 3, if elements of `{A, A, B, B, C, C}` are distinct, i.e. `A != A`, it would be P(6, 3), and having duplicated `{A, A, B}` and `{A, A, B}`, which is unwanted. –  midnite Jul 12 '13 at 21:29
Ah, good point. –  beaker Jul 12 '13 at 21:33
Technically speaking, a set cannot allow repetition –  mor Jul 12 '13 at 21:43
@ricard.m.o., Hmm... do you mean nPr / permutation cannot deal with repeated element? If so, we may have to think in another way. –  midnite Jul 12 '13 at 21:51

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.

-

See this paper that finds a theoretical formula for the number of answers. The paper information is: "Permutations with limited repetitions" by Roberto Frucht from Journal of Combinatorial Theory with doi of 10.1016/S0021-9800(66)80025-X

-

Well, this is a little late, but I have a Java Combinatorics library up on GitHub that will do this. Here is the basic usage:

Include the dependency in your project:

``````<dependency>
<groupId>com.xiantrimble.combinatorics</groupId>
<artifactId>combinatorics</artifactId>
<version>0.2.0</version>
<dependency>
``````

Then iterate the permutations by getting a virtual collection from the combinatoric factory:

``````import com.xiantrimble.combinatorics.CombinatoricFactory;
import com.xiantrimble.combinatorics.CombinatoricFactoryImpl;
import com.xiantrimble.combinatorics.Combinatoric;
...
int k = 6;
int[] domain = {1,1,1,1,2,2,2,3,3,4};
// create a factory.
CombinatoricFactory factory = new CombinatoricFactoryImpl();
Combinatoric<Integer> permutations = factory.createPermutations(k,  domain);

for( Integer[] permutation : permutations ) {
System.out.println(Arrays.toString(permutation));
}
``````

The code does not do a dictionary order, but is instead geared toward trying to minimize the change between consecutive elements, so keep that in mind. Also, there are some improvements in the 0.3.0-SNAPSHOT version, which is available on Sonatype's snapshot repository.

-
user
The text passage primarily discusses the problem of generating permutations with limited repetition, providing examples and discussing potential approaches and algorithms. It also mentions a Java library that can be used to solve this problem.

TYPE: NO_QUESTION

The passage does not contain a direct mathematical question that requires an answer. It is more of a discussion or explanation of a problem and potential solutions. While it mentions calculations and permutations, it does not ask a specific question that needs to be answered within the text.