I'm gonna try something and maybe I am utterly wrong, but hey!
Just because a theory is wrong doesn't mean you've to give it up. ;)
The problem is, that we want to determine the number of elements whose values disagree in both vectors. If we now that number we can half it, since a swap works on two values at once. So my bold statement is, that this is solvable calculating the Hamming-Distance between both vectors:
HammingDistance["CCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDD", "CDCDCCDCDCDCDDCDCDCDCDCDCDCDCDCD"]
this yields 22. So there are 11 swaps necessary to align both vectors perfectly.
Destroy me! ;)
Edit:
If we consider C to be 0 and D to be 1 we're in algebraic coding theory and this becomes a computation over 0,1 (mod 2). So the both vectors can be considered such as:
a = {0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0,
1, 0, 1, 0, 1, 0, 1, 0, 1, 1};
b = {0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 1, 0, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1,
0, 1, 0, 1, 0, 1, 0, 1, 0, 1};
And just because we're curious and want to take a look behind the curtain we don't use HammingDistance from the library, but our own little version:
Count[(-1)^a*(-1)^b, -1]
Which yields again 22 => 11 swaps.
Edit 2:
Let me explain a little my approach. Basically, why this works in your case is of the nice (nearly) alternating pattern of the target vector and the entropy of your alphabet allows mod 2 calculations.
We could for instance create a list of the characters:
s1 = Characters["CCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDD"];
s2 = Characters["CDCDCCDCDCDCDDCDCDCDCDCDCDCDCDCD"];
If we transpose both vectors it yields:
Transpose@{s1, s2}
{{"C", "C"}, {"C", "D"}, {"D", "C"}, {"C", "D"}, {"D", "C"}, {"C", "C"},
{"D", "D"}, {"C", "C"}, {"D", "D"}, {"C", "C"}, {"D", "D"}, {"C", "C"},
{"D", "D"}, {"C", "D"}, {"D", "C"}, {"C", "D"}, {"D", "C"}, {"C", "D"},
{"D", "C"}, {"C", "D"}, {"D", "C"}, {"C", "D"}, {"D", "C"}, {"C", "D"},
{"D", "C"}, {"C", "D"}, {"D", "C"}, {"C", "D"}, {"D", "C"}, {"C", "D"},
{"D", "C"}, {"D", "D"}
}
If we extract the positions where the tuples are equal:
Position[trans, {a_, a_}]
we get
{{1}, {6}, {7}, {8}, {9}, {10}, {11}, {12}, {13}, {32}}
Between tuple 1 and 6 there are 4 numbers and between tuple 13 and 32 are 18. Since a swap operates on two indices at the same time, the amount of adjacent swaps is 22/2 => 11.
Update:
Basically the problem is to find the number of permutation steps to turn one sequence into another. From the above list we can determine the number of cycles needed to permute the initial sequence to the target one.
cycles=FindPermutation[s1, s2]
Cycles[{{2, 3}, {4, 5}, {14, 15}, {16, 17}, {18, 19}, {20, 21},
{22, 23}, {24, 25}, {26, 27}, {28, 29}, {30, 31}}]
First[cycles]//Length
=> 11
So 11 adjacent inversions.
If we apply the found cycles:
Permute[s1, cycles]
=> {"C", "D", "C", "D", "C", "C", "D", "C", "D", "C", "D", "C", "D", "D",
"C", "D", "C", "D", "C", "D", "C", "D", "C", "D", "C", "D", "C", "D",
"C", "D", "C", "D"}
Therefore:
(s1 = Permute[s1, cycles]) == s2
=> True
(If we claim, that the vector is a ring structure, we could do even better.
We'd swap the first index with the last, rotate once to the left and solve it in only four adjacent swaps.)
EditDistance
norDamerauLevenshteinDistance
do what you want? $\endgroup$EditDistance
is a bad choice here, for "EditDistance treats transposition as separate deletion and insertion operations", so:EditDistance["ac", "ca"]
yields2
, whereas: "Damerau-Levenshtein distance counts transposition as a single operation" (yields1
) $\endgroup$