vee_sharp's blog

Finding the no of permutations of a string that are palindromes
By vee_sharp, history, 9 years ago, In English

I am trying to find out the the no of permutations possible for a string that are palindrome.The only way I could think of is finding out the possible permutations and then checking if each one of them is palindrome or not. Is there any better way?

  • Vote: I like it
  • -5
  • Vote: I do not like it

»
9 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Note that you need only to permute the first half, then the second half must follow the reversed order of the first half. Also, for a given string the exact characters which will form each half is fixed and you need only to find the number of permutations of the characters forming the first half. Here are some examples. String "ABAG" cannot become a palindrome so answer is 0. String "ABBNAAA" contains 4 'A's, 2 'B's and 1 'N'. This means that N is in the middle and each half contains 2 'A's and 1 'B'. And since that makes 3!/(2!*1!), there are 3 permutations of "ABBNAAA" which are palindromes. And a last one, string "ABBA" contains 2 'A's and 2 'B's, meaning that each half contains 1 'A' and 1 'B' whihc gives 2!/(1!*1!) = 2 permutations :)

→ Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it +13 Vote: I do not like it

Is this a programming problem? Or is it a math problem?

If so, what are your constraints? If the string is guaranteed to be shorter than about 11 characters long then you should definitely do the "brute force" solution as you mentioned (try every permutation and check if it's a palindrome), if it is a programming problem.

But, there is most certainly a better way. It seems more like a combinatorics / counting problem than anything else (recall permutations and combinations from high school or in an introductory algebra class).

Once you are thinking this way, here is an example to get you thinking about it. What do the following strings have in common? abbacac xyyxzxz

They share a similar "pattern" in terms of their characters. The first string has 3 a's, 2 b's and 2 c's. Similarly the second string has 3 x's, 2 y's and 2 z's. Intuitively, these will have the same answer (number of palindromic permutations). Also, the original order doesn't matter (since you will be permuting them.) So the "counts" of the characters are important -- how many of each character appear in the string.

Secondly, a palindrome is special because it is "symmetric" (by definition). Using the "abbacac" example above, can you think of examples of palindromes from this string?

For example: "abcacba" is such a palindrome. You will notice that it has 1 "a" in the middle, and then the remainder of the letters appear around the middle "a" in a mirrored fashion. In fact, ALL palindromes of abbacac have this property:

acbabca
bacacab
bcaaacb
etc.

Try more examples yourself.

Anyway, the point is, since there are an odd number of a's, that odd "a" has to be in the middle. For everything else, there is (and must be) an even number, and half of them appear on the right, and half of them appear on the left.

So, in the above example, we must have 1 a, 1 b, and 1 c appear on the left, and similarly on the right (of the middle a). The order doesn't matter. You can choose any order of them on the left. Once you know the order of the letters on the left, the remaining letters on the right have only one choice (they must appear as the mirror image of the left side).

This holds true in general:

  1. Start by counting how many times each letter appears.
  2. All letters must occur an even number of times (except possibly one letter, which may be odd)
  3. If there is an odd-occurring letter, one occurrence of it must be in the middle
  4. Of the remaining characters, half of them must appear on the left, half on the right.
  5. You can permute the characters in any way on the left, and then there is a single choice of permutation on the right, so that they appear as a mirror image.
  6. So, the number of answers is precisely the number of ways you can permute the left side. This is a classic permutation problem (I think it's called the "multinomial coefficient" or something fancy).

(I won't give you this last part of how to compute the answer. I'm hoping you will remember this from combinatorics classes, or that you will learn something new by trying to derive the formula yourself!)

Good luck.

→ Reply