Enumerating Oriented Gene Orderings(지향된 유전자 순서 배열)

https://rosalind.info/problems/sign/

ROSALIND | Enumerating Oriented Gene Orderings

Problem

A signed permutation of length nn is some ordering of the positive integers {1,2,…,n}{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)π=(5,−3,−2,1,4) is a signed permutation of length 55.

Given: A positive integer n≤6n≤6.

Return: The total number of signed permutations of length nn, 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

 

 이 문제는 순열을 구한 이후, 각 순열의 숫자마다 +-를 매겨야하는 signed 순열을 구하는 문제이다. 이것을 구하는데에 여러 방법이 있겠다만, 필자는 -쪽 숫자도 애초에 순열을 만드는 풀에 포함시키고, 그냥 순열을 구하는 식으로 구했다

def factorial(n):#팩토리얼
    re=1
    for i in range(1,n+1):
        re*=i
    return re

def writing(li):#쓰기형식
    re=''
    for i in li:
        re+=str(i)+' '
    re+='\n'
    return re

def DFS(now):#순열구하기
    if len(now)==n:#순열 끝
        writef.write(writing(now))
        return
    for i in l:
        if i not in now and -i not in now:#+- 따져서 있는거
            now.append(i)
            DFS(now)
            now.pop()

n=int(input())
l=[-x for x in range(1,n+1)]+[x for x in range(1,n+1)]#-+를 애초에 같이 만들기

writef=open(r"C:\Users\s_jangbear\Downloads\answer.txt",'w')#순열의 가짓수
wr=str(factorial(n)*(2**n))+'\n'
writef.write(wr)
DFS([])