集合的反转(reversal of a permutation)
一个集合的反转可以用两个下标表示，如将(4,1,2,6,3,5)变成(4,1,3,6,2,5)的反转，可以用[3,5]来表示。
给定：两个集合 π 和 γ， 长度为10。
输出：从一个集合到另一个集合的反转步数，以及每一步的反转表示。
示例输入:
1 2 3 4 5 6 7 8 9 10
1 8 9 3 2 7 6 5 4 10
示例出:
2
4 9
2 5
有一个问题一开始的例子没有解释清楚，确定下标后中间的子串要反转，例子可以改成将(4,1,2,6,3,5)变成(4,3,6,2,1,5)的反转，可以用[2,5]来表示。 这个问题确认后，第一个功能就是要枚举所有反转：
def _get_reverse_array(s):
'''
Parameters
----------
s: 输入数组, 如 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
Returns
-------
reverse_arrays: [[2, 1, 3, 4, 5, 6, 7, 8, 9, 10], [3, 2, 1, 4, 5, 6, 7, 8, 9, 10], [4, 3, 2, 1, 5, 6, 7, 8, 9, 10]...]
所有元素下标对应的反转数组，如 1,3反转得到 [3, 2, 1, 4, 5, 6, 7, 8, 9, 10], 1,4反转得到 [4, 3, 2, 1, 5, 6, 7, 8, 9, 10]...
'''
reverse_arrays = []
for i in range(len(s) - 1):
for j in range(i + 1, len(s)):
r_list = s[i:j + 1]
r_list.reverse()
reverse_arrays.append(s[:i] + r_list + s[j + 1:])
return reverse_arrays
然后就是从两头向中间一层一层枚举直到能找到交集。
当我们计算两个基因串之间的汉明距离时，只需检查不匹配的符号，就能轻松推断出两个基因串之间进化路径上发生的点突变集合。 然而，在计算反转距离时（见 "反转距离"），我们只能得到两个排列之间的最小反转数。 而按反转排序的计算问题要求我们提供一个将一个排列转变为另一个排列的 最小反转列表。 因此，反转排序包含了反转距离的计算：一旦我们有了反转的最小集合，反转距离就会立即得出。