Sorting by Reversals

Reconstructing Evolutionary Histories

When we calculate the Hamming distance between two genetic strings, we can easily infer a collection of point mutations that occurred on the evolutionary path between the two strings by simply examining the mismatched symbols. However, when calculating the reversal distance (see “Reversal Distance”), we only have the minimum number of reversals separating two permutations.
The computational problem of sorting by reversals demands instead that we provide a minimum list of reversals transforming one permutation into another. As a result, sorting by reversals subsumes the calculation of reversal distance: once we have a minimum collection of reversals, the reversal distance follows immediately.

Problem

A reversal of a permutation can be encoded by the two indices at the endpoints of the interval that it inverts; for example, the reversal that transforms (4,1,2,6,3,5) into (4,1,3,6,2,5) is encoded by [3,5].
A collection of reversals sorts ππ into γγ if the collection contains drev(π,γ)drev(π,γ) reversals, which when successively applied to π yield γ.
Given: Two permutations ππ and γ, each of length 10.
Return: The reversal distance drev(π,γ), followed by a collection of reversals sorting π into γ. If multiple collections of such reversals exist, you may return any one.

Sample Dataset

1 2 3 4 5 6 7 8 9 10
1 8 9 3 2 7 6 5 4 10

Sample Output

2
4 9
2 5

Solution

本题就是通过终点进行回溯操作即可。

from typing import List
class Solution:
    def backtrace(self, d: dict, end: str) -> 'List[parent, reversalRange, child]':
        """从终点逆推到源头，返回经过路径的所有信息，那么路径数组长度 就是反转距离"""
        path = []
        while True:  # 非源头
            path.append(d[end])
            end = d[end][0]
            if d[end][0] == end: break
        return path
    def reversalDistance(self, s: List[int], t: List[int]) -> int:
        if s == t: return []
        s, t = tuple(s), tuple(t)
        # 1. 双源 BFS
        from collections import deque
        d1, d2 = {s: [s, (-1, -1), s]}, {t: [t, (-1, -1), t]}  # 图节点从源节点翻转次数
        q1, q2 = deque([s, ]), deque([t, ])  # 两个队列一起变换
        while q1 or q2:
            for q, sign, set1, set2 in [(q1, s, d1, d2), (q2, t, d2, d1)]:
                for _ in range(len(q)):
                    parent = q.popleft()  # 弹出图节点
                    # 2. 枚举当前序列所有翻转可能
                    for start in range(len(parent)):
                        for end in range(start + 1, len(parent)):
                            child = parent[:start] + parent[start:end+1][::-1] + parent[end+1:]
                            if child not in set1:
                                set1[child] = [parent, (start, end), child]  # 父亲,反转区间,儿子
                                q.append(child)
                            # [s->...->child] [child<-...<-t]
                            if child in set2:
#                                 print('BFS meet at', child)
                                if sign == t:  # t 的 child 遇到 s 路径中的值
                                    set1, set2 = set2, set1
                                s2child = self.backtrace(set1, child)[::-1]  # 翻转
                                child2t = [[end, revRange, start] for start, revRange, end in self.backtrace(set2, child)]
                                return s2child + child2t
data = """
9 3 1 4 2 6 5 10 8 7
2 3 4 6 7 1 8 5 9 10
"""
data = [line for line in data.splitlines() if line]
ss = Solution()
for i in range(0, len(data), 2):
    s = list(map(int, data[i].split()))
    t = list(map(int, data[i+1].split()))
    ret = ss.reversalDistance(s, t)
    print(len(ret))
    for start, revRange, end in ret:
#         print(' '.join(f'{n:02d}' for n in start))
#         print(' '.join('^^' if revRange[0] <= i <= revRange[1] else '  ' for i in range(len(s))), end=' ')
        print(revRange[0] + 1, revRange[1] + 1)
#     if len(ret):
#         print(' '.join(f'{n:02d}' for n in end))
#     print('\n')