Optimized Algorithm for finding permutation of a given String?

Question

In the following code I am finding all possible permutation of a given input string and storing them in a list and then counting the palindromes among them.This is working fine while the input String length is less than 10. But when input String length is larger than 10 it is taking a lot of time to finding permutations. I want to know what can be optimized here to get constant time for execution?

private static char[] inputArray;
private static List<String> listOfpermutations = new ArrayList<>();
private static int count;

public static void main(String s[]) throws IOException {
    BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
    String input = reader.readLine();
    inputArray = input.toCharArray();
    permutation(0);
    for (String combination : listOfpermutations) {
        if (combination.equals(new StringBuilder(combination).reverse().toString())) {
            count++;
        }
    }
    System.out.println(count);
}

public static void permutation(int start) 
{
    String temp = "";
    if (start != 0) {
        if (start == inputArray.length) {
            for (int i = 0; i < start; i++) {
                temp = temp + inputArray[i];
            }
            if (!listOfpermutations.contains(temp)) {
                listOfpermutations.add(temp);
            }
        }

    }
    for (int i = start; i < inputArray.length; i++) 
    {
        swap(start, i);
        permutation(start + 1);
        swap(start, i);
    }
}

static void swap(int pos1, int pos2) {
    char temp = inputArray[pos1];
    inputArray[pos1] = inputArray[pos2];
    inputArray[pos2] = temp;
}

Tested Input:

aaabbb //works awesome
ccccddddcc //works fine
ccccddddcce //here its taking too long

You are using both loop and recursion... You should try to avoid that... — TheLostMind
– TheLostMind, Commented Dec 12, 2013 at 13:18
It is impossible to get constant execution since you are trying to generate n! permutations. The execution time will always grow with n. — Fortunato
– Fortunato, Commented Dec 12, 2013 at 13:23
@DanglingPiyush - using a different data structure will just change the constant value... It might help, but it will not make a major impact... — TheLostMind
– TheLostMind, Commented Dec 12, 2013 at 13:28

Abhishek Bansal · Accepted Answer · 2013-12-12 13:37:22Z

4

IMO this is more of a math question than an algorithmic one.

Since you are only interested in the number of palindromic strings, you need not generate all the possible permutations.

Calculate the number of characters of each type in the string. Divide the characters by two. Calculate the number of permutations of that half string. This will be the answer because the other half of the string simply mirrors this half.

For example if the string is aabbcc, then count of a = 2, count of b = 2 and count of c = 2.

So we halve these to form abc, permute this in 6 ways. This will be the number of permutations of palindrome.

(you will need to check whether the number of characters in the string is odd or even)

edited Dec 12, 2013 at 13:37

answered Dec 12, 2013 at 13:30

Abhishek Bansal

12.7k4 gold badges34 silver badges46 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

Dangling Piyush Over a year ago

What do you mean by each type of String?

Abhishek Bansal Over a year ago

Each type of character in the string. For example if the string is aaabbbccc, then count of a = 3, count b = 3 and count of c = 3.

Dangling Piyush Over a year ago

Awesome plan !! but I will implement this and accept your answer as soon as i get this done.Thanks alot.

chill · Accepted Answer · 2013-12-12 13:57:01Z

You can get a significant improvement in the running time of you don't generate all the n! permutations.

Since you're looking for palindromes, your input data is expected to contain many duplicated characters. The way you generate permutations you will generate many identical ones. (As a side effect, you will count certain permutations several times).

Instead, generate the permutations in lexicographic order

PS. Additionally, you can skip creating the full list, but just check for a palindrome immediately after you've finished generating the next permutation.

PPS. The idea of Abhishek Bansal is rather good, indeed.

Count the number of occurrences of each character in the string. If a palindrome is possible, then all of the characters must have even counts, except perhaps only one.

Divide each count by 2 and create a string with that count, after the division, in alphabetical order. For example, from "abcccabaa" you obtain the string "aabc" (note that c has odd count and it appears once in the new string).

From the resulting string, generate and count all permutations in the lexicographic order. This will be your answer. You don't need to check for palindromes, because you generate all the possible palindromes this way. Each such permutation will represent half of the palindrome. The whole palindrome would be that first half, possibly followed by a single instance of the character with the odd count, the followed with the reversed first half. For example, the first few palindromes would be

"aabc" + "c" + "cbaa"
"aacb" + "c" + "bcaa"
"abac" + "c" + "caba"

followed your advice of immediatle checking for palindrome. This made a significant execution time reduce.Will try to implement your suggested lexicographic order.Thanks for your quick reply.

Chris Gerken · Accepted Answer · 2013-12-12 13:32:10Z

0

Several performance tips:

Decide how large the list will be and pass that size as part of the constructor. You're spending a lot of time growing the list.
Don't use a list at all. Just determine whether the permutation is a palindrome when you construct the permutation.
Try creating unique permutations and then creating a palindrome from the permutation (e.g. "abac" would give you "abacaba"). This should give you the same set as you're getting now.

answered Dec 12, 2013 at 13:32

Chris Gerken

16.4k6 gold badges48 silver badges61 bronze badges

Comments

Aditya · Accepted Answer · 2013-12-12 14:07:16Z

0

There is a better way to do it, which will reduce your time complexity to a great extent.

Steps for implementation:-

First reduce your string to compressed form. For e.g aaabbb reduces to a3b3. ccccddddcc reduces to c6d4.
Next if the length of string is even, then every character must have even count(frequency). If every character doesn't have even count then it is having zero palindromic permutation. And, if the length of string is odd, then their must be exactly one character with odd count(frequency). If atmost one element is not having the odd count then it is having zero palindromic permutation. For e.g., aaabbb
String length - 6 (Even)
But characters 'a' and 'b' have odd count.
Hence, it has zero palindromic permutation.

e.g. ccccddddcc
String length - 10 (Even)
All characters 'c'and 'd' have even count.
Hence, it has palindromic permutations.

e.g. ccccd
String length - 5 (Odd)
Count of 'c' is 4(even) and 'd' has odd count, i.e. 1
Hence, it has palindromic permutations.
Now, in 2nd point you have got to know whether the string has palindromic permutations or not, now we have to only find out how many permutations are there.
When the String is reduced to format like c6d4 and you know that there are permutations existing for it, then you can proceed like here:

for e.g. c4d2 take can be reduce to 3 characters (as 2c and 1d, because in palindrome the rest string is same) and how can they be arranged, so answer is 3!/(2!*1!) = 3

for e.g. c4e4d1 can be reduce to 4 characters (as 2c and 2e, because in palindrome the rest string is same and 1d character would be in between), so answer is 4!/(2!*2!) = 6.

answered Dec 12, 2013 at 14:07

Aditya

1,3441 gold badge13 silver badges25 bronze badges

2 Comments

Dangling Piyush Over a year ago

it has a problem for aaabbbb can you explain in your fourth point how this String will get resolved.In my case it is giving 1 as answer but it should give 3.

Aditya Over a year ago

@DanglingPiyush the String aaabbbb will be reduced to a3b4 and hence we can reduce the string to 2b and 1a, since for string to be palindrome, rest of the string should be reverse of what it is in first half, so if you will look for its permutations it will be, 3!/(2!*1!) = 3.

Collectives™ on Stack Overflow

Optimized Algorithm for finding permutation of a given String?

4 Answers 4

3 Comments

1 Comment

Comments

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

3 Comments

1 Comment

Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related