<p>This is an expanded and corrected version of <a href="https://stackoverflow.com/a/18294951/2144669">Subhasis's answer</a>.</p>

<p>Formally, the problem is, given a <em>n</em>-letter alphabet <em>V</em> and two <em>m</em>-letter words, <em>x</em> and <em>y</em>, for which there exists a permutation <em>p</em> such that <em>p</em>(<em>x</em>) = <em>y</em>, determine the least number of swaps (permutations that fix all but two elements) whose composition <em>q</em> satisfies <em>q</em>(<em>x</em>) = <em>y</em>. Assuming that <em>n</em>-letter words are maps from the set {1, ..., <em>m</em>} to <em>V</em> and that <em>p</em> and <em>q</em> are permutations on {1, ..., <em>m</em>}, the action <em>p</em>(<em>x</em>) is defined as the composition <em>p</em> followed by <em>x</em>.</p>

<p>The least number of swaps whose composition is <em>p</em> can be expressed in terms of the cycle decomposition of <em>p</em>. When <em>j</em><sub>1</sub>, ..., <em>j</em><sub><em>k</em></sub> are pairwise distinct in {1, ..., <em>m</em>}, the cycle (<em>j</em><sub>1</sub> ... <em>j</em><sub><em>k</em></sub>) is a permutation that maps <em>j</em><sub><em>i</em></sub> to <em>j</em><sub><em>i</em> + 1</sub> for <em>i</em> in {1, ..., <em>k</em> - 1}, maps <em>j</em><sub><em>k</em></sub> to <em>j</em><sub>1</sub>, and maps every other element to itself. The permutation <em>p</em> is the composition of every distinct cycle (<em>j</em> <em>p</em>(<em>j</em>) <em>p</em>(<em>p</em>(<em>j</em>)) ... <em>j'</em>), where <em>j</em> is arbitrary and <em>p</em>(<em>j</em>') = <em>j</em>. The order of composition does not matter, since each element appears in exactly one of the composed cycles. A <em>k</em>-element cycle (<em>j</em><sub>1</sub> ... <em>j</em><sub><em>k</em></sub>) can be written as the product (<em>j</em><sub>1</sub> <em>j</em><sub><em>k</em></sub>) (<em>j</em><sub>1</sub> <em>j</em><sub><em>k</em> - 1</sub>) ... (<em>j</em><sub>1</sub> <em>j</em><sub>2</sub>) of <em>k</em> - 1 cycles. In general, every permutation can be written as a composition of <em>m</em> swaps minus the number of cycles comprising its cycle decomposition. A straightforward induction proof shows that this is optimal.</p>

<p><strong>Now we get to the heart of Subhasis's answer.</strong> Instances of the asker's problem correspond one-to-one with <strong>Eulerian</strong> (for every vertex, in-degree equals out-degree) digraphs <em>G</em> with vertices <em>V</em> and <em>m</em> arcs labeled 1, ..., <em>m</em>. For <em>j</em> in {1, ..., <em>n</em>}, the arc labeled <em>j</em> goes from <em>y</em>(<em>j</em>) to <em>x</em>(<em>j</em>). The problem in terms of <em>G</em> is to determine how many parts a partition of the arcs of <em>G</em> into directed cycles can have. (Since <em>G</em> is Eulerian, such a partition always exists.) This is because the permutations <em>q</em> such that <em>q</em>(<em>x</em>) = <em>y</em> are in one-to-one correspondence with the partitions, as follows. For each cycle (<em>j</em><sub>1</sub> ... <em>j</em><sub><em>k</em></sub>) of <em>q</em>, there is a part whose directed cycle is comprised of the arcs labeled <em>j</em><sub>1</sub>, ..., <em>j</em><sub><em>k</em></sub>.</p>

<p><strong>The problem</strong> with Subhasis's NP-hardness reduction is that arc-disjoint cycle packing on <em>Eulerian</em> digraphs is a special case of arc-disjoint cycle packing on general digraphs, so an NP-hardness result for the latter has no direct implications for the complexity status of the former. In <a href="http://arxiv.org/abs/1402.2137" rel="noreferrer">very recent work</a> (see the citation below), however, it has been shown that, indeed, even the Eulerian special case is NP-hard. Thus, by the correspondence above, the asker's problem is as well.</p>

<p>As Subhasis hints, this problem can be solved in polynomial time when <em>n</em>, the size of the alphabet, is fixed (fixed-parameter tractable). Since there are <em>O</em>(<em>n</em>!) distinguishable cycles when the arcs are unlabeled, we can use dynamic programming on a state space of size <em>O</em>(<em>m</em><sup><em>n</em></sup>), the number of distinguishable subgraphs. In practice, that might be sufficient for (let's say) a binary alphabet, but if I were to try to try to solve this problem exactly on instances with large alphabets, then I likely would try branch and bound, obtaining bounds by using linear programming with column generation to pack cycles fractionally.</p>

<pre><code>@article{DBLP:journals/corr/GutinJSW14,
  author    = {Gregory Gutin and
               Mark Jones and
               Bin Sheng and
               Magnus Wahlstr{\"o}m},
  title     = {Parameterized Directed \$k\$-Chinese Postman Problem and \$k\$
               Arc-Disjoint Cycles Problem on Euler Digraphs},
  journal   = {CoRR},
  volume    = {abs/1402.2137},
  year      = {2014},
  ee        = {http://arxiv.org/abs/1402.2137},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
</code></pre>
Finding the minimum number of swaps to convert one string to another, where the strings may have repeated characters
<p>I was looking through a programming question, when the following question suddenly seemed related.</p>

<p>How do you convert a string to another string using as few swaps as follows. The strings are guaranteed to be interconvertible (they have the same set of characters, this is given), <strong>but the characters can be repeated</strong>. I saw web results on the same question, without the characters being repeated though.
Any two characters in the string can be swapped. </p>

<p>For instance : "aabbccdd" can be converted to "ddbbccaa" in two swaps, and "abcc" can be converted to "accb" in one swap.</p>

<p>Thanks! </p>