Rosalind - Reversal Distance

Sep 26, 2020 rosalind

Problem:

Please find the problem here.

Solution:

This is a tough problem, I handled it using a few techniques.

The problem hinted on brute force, in order to make sure it runs within the allocated time, it is easy to just pre-compute the solutions.

The set of all solutions is daunting (10!) squared. I make one observation to make it simple - the symbol themselves does not matter, we could rename all the symbols consistently and we will get exactly the same reversal distance. Therefore, I reduced the problem of finding the distances between all pairs to the distance of all permutations to a canonical one. That makes the problem much smaller.

The first code consumed the pre-computed result and output distance as needed. The key variables are the parents. Parents represent the shortest path tree, following the parent pointers, it reaches the root in the shortest path. (The reason why we don’t simply pre-compute the distances is to make it possible to solve the next problem)

The parents are computed using BFS in the second code, that is just the standard BFS. A permutation is represented by the number and the representation is encoded by a number using the encode/decode functions. 

The encode and decode functions implements Lehmer’s code. That code maps the set of permutations into the range [0, n!), making it very convenient to use.

Code: