Reversal Distance

Rearrangements Power Large-Scale Genomic Changes

Perhaps the most common type of genome rearrangement is an inversion, which flips an entire interval of DNA found on the same chromosome. As in the case of calculating Hamming distance (see “Counting Point Mutations”), we would like to determine the minimum number of inversions that have occurred on the evolutionary path between two chromosomes. To do so, we will use the model introduced in “Enumerating Gene Orders” in which a chromosome is represented by a permutation of its synteny blocks.
Problem
A reversal of a permutation creates a new permutation by inverting some interval of the permutation; (5,2,3,1,4)(5,2,3,1,4), (5,3,4,1,2)(5,3,4,1,2), and (4,1,2,3,5)(4,1,2,3,5) are all reversals of (5,3,2,1,4)(5,3,2,1,4). The reversal distance between two permutations ππ and σσ, written drev(π,σ)drev(π,σ), is the minimum number of reversals required to transform π into σ (this assumes that ππ and σσ have the same length).
Given: A collection of at most 5 pairs of permutations, all of which have length 10.
Return: The reversal distance between each permutation pair.
Sample Dataset

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

Sample Output
9 4 5 7 0

Hint

Don’t be afraid to try an ugly solution.

贪心错误！

题意规定 A reversal of a permutation 意思是某个全排列区间 [i, j] 的所有数字发生翻转。然后 reversal distance 定义是一个全排列 π 通过连续进行 n 次区间 [i, j] （可重叠）翻转获得另一个全排列 σ 的次数。

3 10 8 2 5 4 7 1 6 9
5 2 3 1 7 4 10 8 6 9
3 10 8 2 5 4 7 1 6 9
5 2 3 1 7 4 10 8 6 9
|---|                 将末尾 3 反转到头部
3 10 8 2 5 4 7 1 6 9
3 2 5 1 7 4 10 8 6 9
  |---------|         将末尾 10 反转到头部
3 10 8 2 5 4 7 1 6 9
3 10 4 7 1 5 2 8 6 9
     |---------|      将末尾 8 反转到头部
3 10 8 2 5 4 7 1 6 9
3 10 8 2 5 1 7 4 6 9
           |---|      将末尾 4 反转到头部
3 10 8 2 5 4 7 1 6 9
3 10 8 2 5 4 7 1 6 9

因此暴力的方法就是假设区间 内都有 成立，再依次检测 是否相等，不相等则在 中找到 。由于题目给定全排列不包含重复数字且有答案，因此 是唯一存在的！因此将 进行翻转使得 。

from typing import List
class Solution:
    def reversalDistance(self, s: List[int], t: List[int]) -> int:
        distance = 0
        for i in range(len(s)):
            if s[i] != t[i]:
                distance += 1
                for j in range(i + 1, len(t)):
                    if s[i] == t[j]:
                        t[i:j+1] = reversed(t[i:j+1])
                        break
        return distance
data = """
8 6 7 9 4 1 3 10 2 5
8 2 7 6 9 1 5 3 10 4
"""
data = [line for line in data.splitlines() if line]
# print(data)
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()))
    print(s, t)
    print(ss.reversalDistance(s, t))

但是上面输出 7 是错误的！

s : [8, 6, 7, 9, 4, 1, 3, 10, 2, 5]
t1: [8, 2, 7, 6, 9, 1, 5, 3, 10, 4]
        |-----|
t2: [8, 6, 7, 2, 9, 1, 5, 3, 10, 4]
s : [8, 6, 7, 9, 4, 1, 3, 10, 2, 5]
t1: [8, 6, 7, 2, 9, 1, 5, 3, 10, 4]
              |--|
t2: [8, 6, 7, 9, 2, 1, 5, 3, 10, 4]
s : [8, 6, 7, 9, 4, 1, 3, 10, 2, 5]
t1: [8, 6, 7, 9, 2, 1, 5, 3, 10, 4]
                 |---------------|
t2: [8, 6, 7, 9, 4, 10, 3, 5, 1, 2]
s : [8, 6, 7, 9, 4, 1, 3, 10, 2, 5]
t1: [8, 6, 7, 9, 4, 10, 3, 5, 1, 2]
                    |---------|
t2: [8, 6, 7, 9, 4, 1, 5, 3, 10, 2]
s : [8, 6, 7, 9, 4, 1, 3, 10, 2, 5]
t1: [8, 6, 7, 9, 4, 1, 5, 3, 10, 2]
                       |--|
t2: [8, 6, 7, 9, 4, 1, 3, 5, 10, 2]
s : [8, 6, 7, 9, 4, 1, 3, 10, 2, 5]
t1: [8, 6, 7, 9, 4, 1, 3, 5, 10, 2]
                          |---|
t2: [8, 6, 7, 9, 4, 1, 3, 10, 5, 2]
s : [8, 6, 7, 9, 4, 1, 3, 10, 2, 5]
t1: [8, 6, 7, 9, 4, 1, 3, 10, 5, 2]
                              |--|
t2: [8, 6, 7, 9, 4, 1, 3, 10, 2, 5]

单源 BFS

from typing import List
class Solution:
    def reversalDistance(self, s: List[int], t: List[int]) -> int:
        if s == t: return 0
        s, t = tuple(s), tuple(t)
        # 1. 单源 BFS
        from collections import deque
        distance = 0
        visited = {s, } # 图节点从源节点翻转次数
        q = deque([s, ])  # 两个队列一起变换
        while q:
            distance += 1  # 进队列就多义词转换
            for _ in range(len(q)):
                s = q.popleft()  # 弹出图节点
                # 2. 枚举当前序列所有翻转可能
                for start in range(len(s)):
                    for end in range(start + 1, len(s)):
                        ss = s[:start] + s[start:end+1][::-1] + s[end+1:]
                        if ss == t:
                            return distance
                        if ss not in visited:
                            visited.add(ss)
                            q.append(ss)
        return -1
data = """
1 2 3 4 5 6 7 8 9 10
3 1 5 2 7 4 9 6 10 8
3 10 8 2 5 4 7 1 6 9
5 2 3 1 7 4 10 8 6 9
8 6 7 9 4 1 3 10 2 5
8 2 7 6 9 1 5 3 10 4
3 9 10 4 1 8 6 7 5 2
2 9 8 5 1 7 3 4 6 10
1 2 3 4 5 6 7 8 9 10
1 2 3 4 5 6 7 8 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()))
    print(s, t)
    print(ss.reversalDistance(s, t))

双源 BFS

from typing import List
class Solution:
    def reversalDistance(self, s: List[int], t: List[int]) -> int:
        if s == t: return 0
        s, t = tuple(s), tuple(t)
        # 1. 双源 BFS
        from collections import deque
        distance = 0
        d1, d2 = {s: 0}, {t: 0}  # 图节点从源节点翻转次数
        q1, q2 = deque([s, ]), deque([t, ])  # 两个队列一起变换
        while q1 or q2:
            distance += 1  # 进队列就多义词转换
            for _ in range(len(q1)):
                s = q1.popleft()  # 弹出图节点
                # 2. 枚举当前序列所有翻转可能
                for start in range(len(s)):
                    for end in range(start + 1, len(s)):
                        ss = s[:start] + s[start:end+1][::-1] + s[end+1:]
                        if ss in d2:
                            return distance + d2[ss]
                        if ss not in d1:
                            d1[ss] = distance
                            q1.append(ss)
            for _ in range(len(q2)):
                t = q2.popleft()  # 弹出图节点
                # 2. 枚举当前序列所有翻转可能
                for start in range(len(t)):
                    for end in range(start + 1, len(t)):
                        tt = t[:start] + t[start:end+1][::-1] + t[end+1:]
                        if tt in d1:
                            return distance + d1[tt]
                        if tt not in d2:
                            d2[tt] = distance
                            q2.append(tt)
        return -1
data = """
1 2 3 4 5 6 7 8 9 10
3 1 5 2 7 4 9 6 10 8
3 10 8 2 5 4 7 1 6 9
5 2 3 1 7 4 10 8 6 9
8 6 7 9 4 1 3 10 2 5
8 2 7 6 9 1 5 3 10 4
3 9 10 4 1 8 6 7 5 2
2 9 8 5 1 7 3 4 6 10
1 2 3 4 5 6 7 8 9 10
1 2 3 4 5 6 7 8 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()))
    print(s, t)
    print(ss.reversalDistance(s, t))

速度对比：

b07@SB:~$ time python ./test.py
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10] [3, 1, 5, 2, 7, 4, 9, 6, 10, 8]
9
[3, 10, 8, 2, 5, 4, 7, 1, 6, 9] [5, 2, 3, 1, 7, 4, 10, 8, 6, 9]
4
[8, 6, 7, 9, 4, 1, 3, 10, 2, 5] [8, 2, 7, 6, 9, 1, 5, 3, 10, 4]
5
[3, 9, 10, 4, 1, 8, 6, 7, 5, 2] [2, 9, 8, 5, 1, 7, 3, 4, 6, 10]
7
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10] [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
0
real    3m7.231s
user    3m6.420s
sys     0m0.810s
b07@SB:~$ time python ./test.py
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10] [3, 1, 5, 2, 7, 4, 9, 6, 10, 8]
9
[3, 10, 8, 2, 5, 4, 7, 1, 6, 9] [5, 2, 3, 1, 7, 4, 10, 8, 6, 9]
4
[8, 6, 7, 9, 4, 1, 3, 10, 2, 5] [8, 2, 7, 6, 9, 1, 5, 3, 10, 4]
5
[3, 9, 10, 4, 1, 8, 6, 7, 5, 2] [2, 9, 8, 5, 1, 7, 3, 4, 6, 10]
7
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10] [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
0
real    0m2.132s
user    0m2.072s
sys     0m0.060s

路径求解

我们知道上面翻转次数，但是如何求解最优路径呢？

9
01 02 03 04 05 06 07 08 09 10
^^ ^^                         0 1
02 01 03 04 05 06 07 08 09 10
^^ ^^ ^^                      0 2
03 01 02 04 05 06 07 08 09 10
      ^^ ^^                   2 3
03 01 04 02 05 06 07 08 09 10
      ^^ ^^ ^^                2 4
03 01 05 02 04 06 07 08 09 10
            ^^ ^^             4 5
03 01 05 02 06 04 07 08 09 10
                     ^^ ^^ ^^ 7 9
03 01 05 02 06 04 07 10 09 08
               ^^ ^^ ^^       5 7
03 01 05 02 06 10 07 04 09 08
               ^^ ^^ ^^ ^^    5 8
03 01 05 02 06 09 04 07 10 08
            ^^ ^^ ^^ ^^       4 7
03 01 05 02 07 04 09 06 10 08
4
03 10 08 02 05 04 07 01 06 09
   ^^ ^^ ^^ ^^                1 4
03 05 02 08 10 04 07 01 06 09
         ^^ ^^ ^^ ^^ ^^       3 7
03 05 02 01 07 04 10 08 06 09
^^ ^^ ^^                      0 2
02 05 03 01 07 04 10 08 06 09
^^ ^^                         0 1
05 02 03 01 07 04 10 08 06 09
5
08 06 07 09 04 01 03 10 02 05
         ^^ ^^ ^^ ^^ ^^ ^^    3 8
08 06 07 02 10 03 01 04 09 05
   ^^ ^^ ^^                   1 3
08 02 07 06 10 03 01 04 09 05
                     ^^ ^^ ^^ 7 9
08 02 07 06 10 03 01 05 09 04
                  ^^ ^^       6 7
08 02 07 06 10 03 05 01 09 04
            ^^ ^^ ^^ ^^ ^^    4 8
08 02 07 06 09 01 05 03 10 04
7
03 09 10 04 01 08 06 07 05 02
^^ ^^ ^^                      0 2
10 09 03 04 01 08 06 07 05 02
^^ ^^ ^^ ^^ ^^ ^^             0 5
08 01 04 03 09 10 06 07 05 02
   ^^ ^^ ^^ ^^ ^^ ^^ ^^       1 7
08 07 06 10 09 03 04 01 05 02
   ^^ ^^ ^^ ^^                1 4
08 09 10 06 07 03 04 01 05 02
            ^^ ^^ ^^          4 6
08 09 10 06 04 03 07 01 05 02
      ^^ ^^ ^^ ^^ ^^ ^^ ^^ ^^ 2 9
08 09 02 05 01 07 03 04 06 10
^^ ^^ ^^                      0 2
02 09 08 05 01 07 03 04 06 10
0

请见下一个题目