CODEWITHSUNDEEP
javaarraysalgorithmmathpermutation
midnite
midnite

Reputation: 5286

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.

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.

Upvotes: 5

Views: 2954

Answers (4)

Joe
Joe

Reputation: 1

You can think of permutations as binary carry processing. For example, 0000,0001,0010 in binary.

 public static int[][] permutation(int size,int carryNum) {
    if(size == 0)
        return new int[0][0];

    int s = size - 1;
    int cNum = carryNum - 1;
    int s1 = 1;
    for(int i=0;i<size;i++){
        s1 = s1 * carryNum ;
    }
    int[][] commands = new int[s1][size];
    for (int i = 1; i < s1; i++) {

        for (int j = s; j >= 0; j--) {
            commands[i][j] = commands[i - 1][j];
        }

        for (int j = s; j >= 0; j--) {
            int last = commands[i][j];
            if ((last + 1) > cNum) {
                commands[i][j] = 0;
            } else {
                commands[i][j] = last + 1;
                break;
            }
        }
    }
    return commands;
}

public static void main(String[] args) {

    int[][] s = permutation(7,3);
    for (int[] command : s) {
        System.out.println(Arrays.toString(command));
    }
}

output result:

[0, 0, 0, 0, 0, 0, 0]

[0, 0, 0, 0, 0, 0, 1]

[0, 0, 0, 0, 0, 0, 2]
          .
          .
          .
[0, 0, 0, 0, 2, 0, 2]

[2, 2, 2, 2, 2, 2, 2]

Upvotes: 0

Masood_mj
Masood_mj

Reputation: 1184

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

Upvotes: 0

Christian Trimble
Christian Trimble

Reputation: 2136

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.

Upvotes: 1

user545199
user545199

Reputation:

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.

Upvotes: 1

Related Questions