I have a string lets say abcd so its all permutations would be

abcd    bacd    cabd    dabc
abdc    badc    cadb    dacb
acbd    bcad    cbad    dbac
acdb    bcda    cbda    dbca
adbc    bdac    cdab    dcab
adcb    bdca    cdba    dcba

But out of these 24 permutations, all permutations of abcd are same to abcd if maximum 2 swaps and minimum 0 swaps are applied on them. By swap I means I can interchange two characters and these characters can be any two characters in the string. Let me explain through example

1. abcd

No characters are required to be swapped as abcd is already copy of abcd.

2. acbd 

If I will swap c and b, then string will become abcd. So it means string acbd is copy of abcd.

3. cabd

If I will swap c and a, string will become acbd and then if I swap c and b, string will become abcd which is copy of abcd.

4. dcab

This string after 2 swaps also can't be converted to abcd so this is not a copy of abcd.

All I want to know is, if I am given a string str, how many strings are there which are permutations of str but can't be converted to str after maximum of two swaps. My approach for this problem was finding all permutations of string str and then proceeding but for string with larger length, it fails. Please help so that I can proceed to this problem.

  • Consider thinking of permutations from the viewpoint of algebra and the symmetric group $S_n$. You ask how many permutations exist which can not be expressed as a transposition, the identity, or as a product of two transpositions. Pick what the transpositions are, taking into account if the transpositions do or don't overlap. – JMoravitz Mar 14 '16 at 19:14

I'll give a hint since I think you've largely answered your own question already, if what you say is correct (that you can "reach" any permutation of $ABCD$ with at most two swaps).

Based on this alone, I'd say that the number of such permutations (of an $N$-character string) that cannot be reached are those that have more than four characters different from the original string.

The first swap can touch two characters. The second swap can touch two different characters. And ... that's all you can touch.

So count up the number of permutations that have (a) exactly two characters in different locations, (b) exactly three characters in different locations, and (c) exactly four characters in different locations. Subtract this sum from the total number of permutations. (Don't forget to count the original string!)

This is fairly quick for strings with $N$ unique characters. It gets a bit more complicated if some characters repeat, as in the string $REPEAT$ or $MISSISSIPPI$.

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.