-1

We are provided with a string A (may contain repeated characters as well ). One needs to make all possible permutations of A , and find out how many pairs of strings chosen from these permutations are not similar.

Two strings are similar if we can make both of them exactly same by carrying out at most 1 swap in each of them .

Example :- if we are provided with string abcd , then for permutation abcd , the permutations which are not similar to it are bcda , bdac , cadb , cdba , dabc , dcab . Similar is the case for other permuations as well. So overall number of desired pairs are 24*6=144 .

I tried solving it for each possible pair by approach mentioned here https://stackoverflow.com/questions/18292202/finding-the-minimum-number-of-swaps-to-convert-one-string-to-another-where-the

But as the permutations can be large enough , I need a better approach of solving this.

Community
  • 1
user249117
  • 245

1 Answers1

1

I'll assume that, as in your example, the string contains distinct letters; otherwise things would get messy.

Performing at most one swap in each string is equivalent to performing at most two swaps in one string. So we're looking for the number of permutations that can be represented as a product of at most two transpositions.

These are the identity, of which there is $1$, the transpositions, of which there are $\binom n2$, the $3$-cycles, of which there are $2\binom n3$, and the pairs of disjoint transpositions, of which there are $\frac12\binom n{2,2,n-4}$. Thus, in total there are

\begin{align} &1+\binom n2+2\binom n3+\frac12\binom n{2,2,n-4}\\ ={}&1+\frac{n(n-1)}2+\frac{n(n-1)(n-2)}3+\frac{n(n-1)(n-2)(n-3)}8\\ ={}&\frac{3n^4-10n^3+21n^2-14n+24}{24} \end{align}

strings similar to any given string, which in your example comes out to $18$ as expected.

joriki
  • 238,052
  • Thanks for the response . But can't this be generalised or is there some technique to find the answer even if we allow duplicates? – user249117 Mar 06 '16 at 09:57
  • @user249117: It can be done, but it would be a very messy count. You need to eliminate all the doubly counted permutations -- e.g. if you apply a $3$-cycle to $aab$, that's the same as just swapping the $b$ with one of the $a$s -- and the number of such duplications depends on all the counts of repeated letters. In my view, this sort of thing is best done by computer. If you're looking for a solution for repeated letters, I can delete this answer to attract more answers, if you prefer. – joriki Mar 06 '16 at 10:00
  • no there is no need to remove the answer . The answer is perfect for distinct letter strings :) . It would have been better if someone can explain the programming approach to this , as to how to handle such duplicate cases ? Or can you please explain taking some example of such a string . Anyways the same approach will be used for every string. So , it would have been better if someone told me step by step approach on some example of duplicate string . – user249117 Mar 06 '16 at 13:08
  • @user249117: For the programming approach, it depends on the size of problems you want to solve, and thus the degree of sophistication and optimisation you need. A simple approach would be to apply all the permutations described in my answer to the string and count the distinct strings that result. This would be feasible for strings up to a length of about $100$ or so. – joriki Mar 06 '16 at 13:34