Repeat Swap Algorithm

Question

Is there an algorithm for listing all permutations with limited repetition? If there is an existing Java library, that would be so nice!

Say we have 3 elements {A, B, C} . We want a permutation of two elements. This will be ₃ P ₂ :

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

But if we allow maximum repetition twice. How would that be? (I really do not know.)

I am trying to render, we get a permutation 2 from the set {A, A, B, B, C, C} . It will be ₆ P ₂ = 30. But we must select these duplicates. I did it manually, and it's 9. I don't know how to calculate 9 from math.

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

(Actually, ₃ P ₂ with repetition 2 is not a good example. This is because there are only 2 elements in permutations. No differences between unlimited repetition. ₄ P ₃ with repetition 2 would be a more pleasant example. But it would be difficult to list all the permutations .)

Best example to illustrate: ₄ P ₃ for the 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 ₃ from the set {A, B, C, D} with a repeat 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 web page about a similar thing. But it seems that this requires _n P _n (selection of all elements). In addition, I still need an algorithm for generating and listing permutations.

Thanks for the help!

---

There is actually a “non-smart” approach to implementing programming.

For the set {A, B, C, D} save an additional array int used[0, 0, 0, 0] , which is the number of times each element is used. Increase the counter each time an element is selected, and pass a copy of the array forward (down the call tree). Then, using the recursive approach inspired here , modify it to allow unlimited repetition (without deleting the selected one from the set of elements) and add the if (used[i] <= LIMIT) check if (used[i] <= LIMIT) after for .

This is “not reasonable” and not good enough, because we need an additional array and each time we need to check the number used.

Answer 1

Ok, this is a bit late, but I have a Java Combinatorics library on GitHub that will do this. Here is the main use:

Include the dependency in your project:

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

Then drag the permutations to get the virtual collection from the combinatorial 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 follow the order of the dictionary, but is instead intended to minimize changes between consecutive elements, so keep that in mind. In addition, there are some improvements in version 0.3.0-SNAPSHOT, which is available in the Sonatype snapshot repository.

Answer 2

I have already encountered this problem when creating all possible dial sections. This is essentially the same concept as you. (All combinations of a given size are the same as a set of partitions of this size). I found this document that gave a very fast non-recursive algorithm for generating these combinations without repeating along with the C ++ implementation.

Answer 3

See this document for a theoretical formula for the number of answers. Paper Information: "Constraints with Limited Repetitions" by Roberto Frucht of the Journal of Combinatorial Theory with doi 10.1016 / S0021-9800 (66) 80025-X