java - string permutation without duplication elements

Question

I am using this code https://stackoverflow.com/a/4240323/2655623 to create permutation and do some calculation on each result.

public static void permutation(String str) { 
    permutation("", str); 
}

private static void permutation(String prefix, String str) {
    int n = str.length();

    int p = prefix.length();
    if(p==5){
            //do some calculation for |prefix| = 5
            return;
    }
    for (int i = 0; i < n; i++){
            permutation(prefix + str.charAt(i), str.substring(0, i) + str.substring(i+1, n));
    }
}

this algorithm works great for me. However, I would like to see how I can remove duplicate characters so I don't calculate the prefix with again. for example for

permutation("aacccbbdeeeef");

I will process abcde about

A = 2 * 4*3*2*1 when a----
B = 2 * 4*3*2*1 when b----
C = 3 * 4*3*2*1 when c----
and so on...
// I hope you get the idea

I wonder if i can reduce the amount of duplicate calculation.

One way I thought was to sort the character orders, and only calculate one of each duplicate characters when I use FOR for them.

for (int i = 0; i < n; i++){
    if(i>0 && str.charAt(i) == str.charAt(i-1)) continue;
    permutation.....
}

this worked fine for me as just need the permutation once. It drastically reduce the number of calls when the number of repeated letters are high.

Now, to sum up, I would like to know if

1. is this guarantee than I will not miss any permutation?
2. how can I prevent cases like a(1)ba(2)cd and a(2)ba(1)cd from happening when p=5. As for p=8 or 10, the trick I used will not be that efficient. so what I need to do?

Thank you very much.

Answer 1

1. is this guarantee than I will not miss any permutation?

Yes. If all the repeated characters are in blocks, like "aaabbccccc", the line of code

if(i>0 && str.charAt(i) == str.charAt(i-1)) continue;

is exactly what you need. It will not miss any permutation because it only skips over ones that would have been the same anyway. And it won't repeat any permutation because the equal characters are in blocks.

2. how can I prevent cases like a(1)ba(2)cd and a(2)ba(1)cd from happening when p=5. As for p=8 or 10, the trick I used will not be that efficient. so what I need to do?

I don't see the need to worry about input strings like "abacd" at all. The set of permutations for this string is exactly the same as the set for "aabcd" so it makes sense to sort the string right at the beginning (this will collect repeated characters into blocks), and call permutation("", sortedString);. Doing it this way you can just use the trick you mentioned.

For long strings, it's going to be slow anyway just because there are lots of permutations and also because the method creates lots of string objects. These factors are much more significant that the minor inefficiency created by iterating over a slightly larger range than strictly necessary and using continue.

Answer 2

Simple solution can be to store the characters into a Set (remove duplicates) and read them ;)

Answer 3

public static void permutation(String str) { 
    Set<Character> charsSet = new HashSet<Character>();
    for (int i = 0; i < s.length(); i++){
        Character  c = new Character (s.charAt(i));
        charsSet.add(c);   
    }
    StringBuilder sb = new StringBuilder();
    for (Character  c : charsSet) {
        sb.append(c.charValue());
    }
    permutation("", sb.toString()); 
}

private static void permutation(String prefix, String str) {
    int n = str.length();

    int p = prefix.length();
    if(p==5){
            //do some calculation for |prefix| = 5
            return;
    }
    for (int i = 0; i < n; i++){
            permutation(prefix + str.charAt(i), str.substring(0, i) + str.substring(i+1, n));
    }
}

Answer 4

this is my variant for the "total signed permutations of length n"

Sample Dataset

2

Sample Output

-1 -2

-1 2

1 -2

1 2

-2 -1

-2 1

2 -1

2 1

total: 8

Follow this sample please:

private static int count = 0;

@Test
public void unsignedPermTest(){
    final int unsigendN = 2;
    final int n = unsigendN * 2;

    final int[] arr = new int[n];

    for(int i=1; i<=unsigendN;i++){
        arr[i-1] = i;
        arr[arr.length-i] = -i;
    }

    count = 0;
    permutation(arr, n, unsigendN);
    System.out.println("total: " + count);
}

public static void permutation(final int[] arr, final int n, final int k) {
    permutation(arr, "", n, k);
}

private static void permutation(final int[] arr, final String prefix, final int n, final int k) {

    if (k == 0)
    {
        final String res = prefix.substring(1);

        final String[] chars = res.split(" ");

        for(int i=0; i<chars.length;i++){
            for(int j=i+1; j<chars.length;j++){
                if(chars[i].replace("-", "").equals(chars[j].replace("-", ""))) return;
            }
        }

        count=count+1;
        System.out.println(res);
        return;
    }

    for (int i = 0; i < n; ++i) {
        permutation(arr, prefix + " " + arr[i], n, k - 1);
    }
}