배경지식

이 문제는 Enumerating Gene Orders 문제의 연장선상에 있는 문제입니다. DNA의 재배열(rearrangement)는 점 돌연변이(point mutation)이 조금씩밖에 종의 다양성을 변화시킬 수 있는 것과는 다르게 종을 크게 변화시킬 수 있습니다. 예를 들면 일개 영장류가 인간으로 분화하고, 꼬끼리, 가재, 소, 돼지 등 수많은 종이 존재할 수 있게 된 것도 유전자 재배열에 의하여 이루어졌다고 합니다. 그렇지만 점 돌연변이도 겸상적혈구빈혈증같이 치명적인 질병을 유발할 수 있듯이 긴 DNA 부분이 재배열 되면 대체적으로 치명적입니다. 그래서인지 DNA 재배열은 거의 일어나지 않습니다.
과학자들은 재배열이 잘 일어나지 않는 것을 근거로 비슷한 종은 비슷한 유전자를 가지고 있을 것이라 생각합니다. 그래서 두 종을 비교할 때, 두 종의 DNA가 얼마나 비슷하지를 보죠. 이 때, 과학자들이 종을 비교하기 위해 주목하는 것이 Synteny block 입니다.
(사진 출처: http://rosalind.info/problems/sign/)
과학자들이 두 종을 비교하기 위해서는 아래와 같은 순서를 따릅니다.

1. Synteny Block pair를 찾습니다.
2. 각 pair에 번호를 색인을 답니다. (e.g 1,2,3,4...n)
3. 두 종의 색인의 순서가 얼마만큼 다른지를 봅니다.

이와 같은 방식으로 두 종을 비교할 수가 있습니다.
Enumerating Gene Orders 문제에서는 synteny block을 단순화하기 위해 DNA 나선이 2가닥임에도 불구하고 하나 간주하고 문제를 풀었습니다. 하지만 더 정확하게 염색체를 묘사하기 위해서는 DNA에 방향이 있을음 생각해야 합니다. DNA는 두 가닥이 서로 반대 방향으로 복제 및 전사가 진행되기 때문입니다. 이 문제에서는 이를 반영하여 순열을 구하는 법을 요구합니다.

문제정의

원문

A signed permutation of length n 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, $\pi = (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).

해석

n 값이 주어졌을 때, 정수들 $\{1,2,...,n\}$ 이 각각 양수도 될 수 있고, 음수도 될 수 있다고 했을 때, 순열의 개수와 순서에 상관없이 전체 순열의 경우의 수를 나열하라는 문제로 볼 수 있습니다.

해결법

1. 먼저 -n ~ n 까지 range를 구한다.
2. -n ~ n 까지의 n개의 요소가 있는 순열을 구한다.($_{2n}P_n$ 개)
3. 여기서 문제가 발생하는데, 첫번째로 순열에 0은 존재하지 않는다. 두번째로는 -n ~ n 의 순열을 구한 것이기 때문에 절대값이 같은 부호가 다른 값들이 동시에 들어갈 수 있다. 그러므로, -n ~ -1, 1 ~ n 까지 의 정수들만을 대상 순열을 구하고, 부호가 같은 같은 값들이 들어가지 않도록 제외한다.
   아래는 핵심 코드이다.

def signed_permutations(n):
  # 0 을 제외한다.
  ls = [i for i in range(-n, n+1) if i != 0]
  # 2nPn 순열을 모두 구한다.
  permus = permutations(ls, n)
  for p in permus:
  	# 각 순열의 경우의 수를 nC2 조합을 구한 뒤에 각 조합의 합 중에 0이 없을 경우 통과시킨다.
    if all(map(sum, combinations(p, 2))):
      yield p

전체 코드는 github rosalind_SIGN.ipynb 에 있습니다.