Enumerating Oriented Gene Orderings

Synteny Blocks Have Orientations

In “Enumerating Gene Orders”, we introduced synteny blocks for two different species, which are very similar areas of two species genomes that have been flipped and moved around by rearrangements. In that problem, we used the permutation to model the order of synteny blocks on a single chromosome.

However, each strand of a DNA molecule has an orientation (as RNA transcription only occurs in one direction), and so to more prudently model chromosomes using synteny blocks, we should provide each block with an orientation to indicate the strand on which it is located. Adding orientations to synteny blocks requires us to expand our notion of permutation so that each index in the permutation has its own orientation.

Problem

A signed permutation of length nn is some ordering of the positive integers {1,2,…,n} in which each integer is then provided with either a positive or negative sign (for the sake of simplicity, we omit the positive sign). For example, π=(5,−3,−2,1,4) is a signed permutation of length 5.
Given: A positive integer n≤6.
Return: The total number of signed permutations of length n, followed by a list of all such permutations (you may list the signed permutations in any order).

Sample Dataset

2

Sample Output

8
-1 -2
-1 2
1 -2
1 2
-2 -1
-2 1
2 -1
2 1

Solution 1

交换法全排列：与之前普通交换法唯一区别在于每个数字有 +- ，因此交换一个数字后，进行正数和负数选取。

from typing import List
class Solution:
    def orientedPermute(self, nums: List[int]) -> List[List[int]]:
        n = len(nums)
        res = []
        def backtrace(idx: int) -> None:
            if idx == n:
                res.append(nums[:])
                return
            for j in range(idx, n):
                nums[j], nums[idx] = nums[idx], nums[j]
                # 正数
                backtrace(idx + 1)  
                # 负数
                nums[idx] *= -1
                backtrace(idx + 1)  
                nums[idx] *= -1
                nums[j], nums[idx] = nums[idx], nums[j]
        backtrace(0)
        return res
n = 2
ret = Solution().orientedPermute(list(range(1, n + 1)))
print(len(ret))
for op in ret:
    print(' '.join(map(str, op)))

Solution 2

标记法全排列：

1. 先不考虑负数，假设当前有 n 个数进行全排列，第一个位置有 n 种可能，第二个位置有 n-1 种可能；第 k 个位置有 n-k+1 种可能。
2. 如何防止一个数被重复添加？例如 x 在第 k 位置之前已经被用过，那么第 k 位置上候选人一定没有 x 。（全排列不存在重复数字，若存在重复数字则标记元素下标即可）

如何处理负数呢？其实就是在当前选中数字 y 当作第 k 位置上的数后， 再额外进行一次 -y 当作第 k 位置上的数。

from typing import List
class Solution:
    def orientedPermute(self, nums: List[int]) -> List[List[int]]:
        n = len(nums)
        res = []
        path = []
        visited = [False] * n
        def backtrace() -> None:
            if len(path) == n:
                res.append(path[:])
                return
            for j in range(n):
                if not visited[j]:  # 下标 j 的元素未访问过
                    visited[j] = True  # 正负都用过
                    path.append(nums[j])
                    backtrace()
                    path[-1] *= -1
                    backtrace()
                    path.pop()
                    visited[j] = False  # 撤销访问
        backtrace()
        return res
n = 2
ret = Solution().orientedPermute(list(range(1, n + 1)))
print(len(ret))
for op in ret:
    print(' '.join(map(str, op)))