Enumerating Gene Orders(유전자 순서 열거하기)

https://rosalind.info/problems/perm/

ROSALIND | Enumerating Gene Orders

Problem

A permutation of length nn is an ordering of the positive integers {1,2,…,n}{1,2,…,n}. For example, π=(5,3,2,1,4)π=(5,3,2,1,4) is a permutation of length 55.

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

Return: The total number of permutations of length nn, followed by a list of all such permutations (in any order).

Sample Dataset

3

Sample Output

6
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

 

 이 문제는 7보다 작거나 같은 정수 N이 주어졌을 때 1~N까지의 정수들의 가능한 배열의 개수와 그 배열들을 출력하는 문제이다. 순열의 개수는 N!로 구할 수 있고 배열 자체는 필자는 DFS를 이용하여 재귀를 응용하여 풀었다. 본래 처음엔 배열들을 다 출력하였지만 그러니 7!같은 경우엔 5040개나 나와버려서 파이썬이 퍼져서 텍스트파일로 써서 답안을 제출했다.

def factorial(n):
    f=1
    for i in range(1,n+1):#팩토리얼 구하기
        f*=i
    f=str(f)+'\n'#문자열로 형식맞추기
    file.write(f)#텍스트파일에 쓰기
    return 

def permutation(per):
    if len(per)==N:#배열 끝
        s=''#문자열로 형식맞추기
        for p in per:
            s=s+str(p)+' '
        s=s+'\n'
        file.write(s)#쓰기
        return
    for i in range(1,N+1):
        if i in per:#이미 들어갔다면
            continue
        per.append(i)#끝에 배치
        permutation(per)#다음으로
        per.pop()#끝을 빼기

N=int(input())
lst=[i for i in range(1,N+1)]
file=open(r'파일경로','w')
factorial(N)
permutation([])