6
$\begingroup$

Updated Problem Description

I have a collection of strings $S$ that only contain two (or $m$ in general) kinds of elements: in this case C and D. For all $s\in S$, the length is the same, the number of C is the same (and so does the number of D).

For instance consider the following two strings:

CCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDD

and

CDCDCCDCDCDCDDCDCDCDCDCDCDCDCDCD.

They have the same number of characters, the same number of C and D. Could anyone suggest how can I count the minimum number of neighbor swappings needed to transform from the 1st string to the 2nd string in Mathematica?

Information that is irrelevant to the problem itself: I am doing this to compare how close the best candidate solution obtained by a problem-specific genetic algorithm to the real optimal solution. You are welcome to suggest other measures of "closeness".

Update 1: There is not periodic boundary condition in my problem. I do not treat the string as necklace.

Update 2: In the comments, @Stephen mentioned Kendall tau distance, but I'm not sure whether it applies to my problem considering that there is no order relation between C and D and so many characters in the string are the same one, i.e. there are so many C in one string.

$\endgroup$
7
  • 2
    $\begingroup$ Are you sure that neither EditDistance nor DamerauLevenshteinDistance do what you want? $\endgroup$
    – Mr.Wizard
    Jan 21, 2014 at 7:37
  • $\begingroup$ I think EditDistance is a bad choice here, for "EditDistance treats transposition as separate deletion and insertion operations", so: EditDistance["ac", "ca"] yields 2, whereas: "Damerau-Levenshtein distance counts transposition as a single operation" (yields 1) $\endgroup$ Jan 21, 2014 at 7:43
  • $\begingroup$ If you have ACM access, 'Adjacent Swaps on Strings', Chitturi et. al. has what you're looking for. $\endgroup$
    – ciao
    Jan 21, 2014 at 9:22
  • $\begingroup$ @rasher, thanks for the information! It looks a bit overwhelming to me though. Actually what I set out to do is to compare the real optimal solution and the best one obtained by various GAs and see how closer those solutions found by GAs to the real optimum. $\endgroup$
    – wdg
    Jan 21, 2014 at 17:38
  • $\begingroup$ Do you always have only two kinds of characters or can you have an arbitrary number of them? In other words, do you have only C and D, or do you also have string with three of them, e.g. C,D,E? $\endgroup$
    – Szabolcs
    Jan 21, 2014 at 19:49

3 Answers 3

4
$\begingroup$

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.)

$\endgroup$
3
  • $\begingroup$ Stefan: HammingDistance["aac", "caa"]/2 = 1. Can you show how "aac" can then be transformed into "caa" in one adjacent swap? $\endgroup$
    – ciao
    Jan 21, 2014 at 11:00
  • $\begingroup$ Obviously, but in the OP, there is no specification of treating the strings as necklaces. $\endgroup$
    – ciao
    Jan 21, 2014 at 12:06
  • 2
    $\begingroup$ and, nonetheless, irrelevant. Take, e.g., {c,c,c,a,a,a} and {a,a,a,c,c,c} with a Hamming of 6. Show how it can be done in 3 swaps allowing the ends to be 'neighbors'... $\endgroup$
    – ciao
    Jan 21, 2014 at 12:14
3
$\begingroup$

First, a brute force approach, suitable only for short strings. Suppose we list all possible permutations of the string, and look at which permutations are accessible from each other via a single neighbour-swap.

s1 = {0, 1, 0, 1, 0, 1, 0, 1};
s2 = {1, 1, 1, 1, 0, 0, 0, 0};

p = Permutations[s1];

g = Graph@Reap[Do[
     If[MatchQ[p[[i]] - p[[j]], {(0) ..., -1, 1, (0) ...}],
      Sow[UndirectedEdge[i, j]]],
     {i, Length[p]}, {j, Length[p]}]][[2, 1]]

enter image description here

The shortest path from s1 to s2 can now be obtained using FindShortestPath:

path = FindShortestPath[g, Position[p, s1][[1, 1]], Position[p, s2][[1, 1]]]
(* {1, 2, 5, 6, 16, 19, 20, 55, 65, 69, 70} *)

The number of steps is

Length[path] - 1
(* 10 *)

The transformation can be visualised:

Module[{steps, flip},
 steps = p[[path]];
 flip = Abs[steps - RotateRight[steps]];
 flip[[1]] *= 0;
 Panel@Grid@MapThread[Style[#1, #2 /. {0 -> Black, 1 -> Red}, Bold] &, {steps, flip}, 2]]

enter image description here

This approach cannot be used for the OP's example, as it will require more memory than there is in the entire universe. However, we can see that the transformation consists of "chains" of neighbour-swaps which "walk" mismatched characters from their initial to their final positions. This can perhaps be seen more easily by looking at the difference of the strings:

s1 - s2
(* {-1, 0, -1, 0, 0, 1, 0, 1} *)

The -1s correspond to locations where there is a zero in the first string but a one in the second. Conversely the 1s in the difference list correspond to positions where there is a one in the first string and a zero in the second. The transformation must "walk" the zeros from the -1 locations to the 1 locations. The total number of steps is thus the combined "walk" distance from the -1 positions to the 1 positions, in this case 10 steps:

enter image description here

Therefore I tentatively conclude that the minimum number of steps to transform s1 to s2 is given by:

Total@Abs[Flatten[Position[s1 - s2, 1]] - Flatten[Position[s1 - s2, -1]]]
(* 10 *)

For the example in the OP we get:

s1 = {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};
s2 = {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};
Total@Abs[Flatten[Position[s1 - s2, 1]] - Flatten[Position[s1 - s2, -1]]]

(* 11 *)

I cannot prove that my formula is correct, so counter-examples are welcome :-)

$\endgroup$
0
$\begingroup$

I think the following works for this simple example:

str1 = "CCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDD";
str2 = "CDCDCCDCDCDCDDCDCDCDCDCDCDCDCDCD";

Length@Cases[
             Length /@ Union /@ Transpose@Characters[{str1, str2}],2 
            ]/2

11

I'm sure there is a simpler way and I may well be missing some flaw in my logic...

$\endgroup$
1
  • $\begingroup$ Could you please explain your logic in words? It's rather hard to understand through your code. $\endgroup$
    – wdg
    Jan 26, 2014 at 9:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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