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:

1. aaabbb //works awesome
2. ccccddddcc //works fine
3. ccccddddcce //here its taking too long

Answer 1

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

Steps for implementation:-

1. First reduce your string to compressed form. For e.g aaabbb reduces to a3b3. ccccddddcc reduces to c6d4.

2. 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.

3. 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.

4. 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.

Answer 2

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"

Answer 3

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)

Answer 4

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.