3

Say I have a bunch of string pairs, representing "before" and "after" values. To give a simple example:

 aaaabbbb -> aabbbbaa
 abbbbbbb -> bbbbbbab
 aaabbbaa -> abbbaaaa
 cccccccc -> cccccccc

How would I determine that one possible permutation could be [ 6, 7, 0, 1, 2, 3, 4, 5 ], or in other words, all the characters were rotated left by two spaces?

Is there some literature on this problem? Also, would there be the concept of a "most likely" permutation, if some pairs in the list don't match up precisely? Could more complicate permutations be found, other than shifting left and right?

Mo Tao
  • 1,225
  • 1
  • 8
  • 17
Derek Ross
  • 75
  • 5

2 Answers2

1

A common solution to the string rotation problem is to concatenate the original string with itself and check if the test string is a substring.

Ex: abcd rotated left two is cdab. So abcd concatenated with itself is abcdabcd, notice cdab is a substring.

I suppose to detect that it is exactly a rotation by two to the left, you could check if the substring starts at the third character. You may need to check a few other cases to confirm that it isn't a rotation in the other direction though.

Community
  • 1
  • 1
Justin Hellreich
  • 575
  • 5
  • 15
  • Thanks, I was also thinking in the general sense, where any permutation other than shifting might be in effect. (Also added an edit). – Derek Ross Feb 09 '17 at 03:24
1

You need to know the basic concepts of graph theory and matching.

Say each position of before is a left node and each position of after is a right node. For left position i and right position j, connect an edge from left node i to right node j, if and only if x[i] equals to y[j] in all pairs x -> y. Then the problem becomes finding a perfect matching of this bipartite graph, which is a solved problem.

"most likely" permutation would be much harder and it requires the exact definition of "most likely". Would you like to satisfy as many pairs as possible? or more matched characters are preferred?

Mo Tao
  • 1,225
  • 1
  • 8
  • 17