Find unknown permutation from string pairs

Question

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?

Answer 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?