[Rosalind] Enumerating Gene Orders (Python)

Rearrangements Power Large-Scale Genomic Changes

• 개놈의 재배열은 이후 표현형에 치명적이거나 심각한 손상을 입힌다. 특히 유사한 DNA구간(한 염색체 내) 간의 재배열을 많이 볼 수 있다. 이때 각 유전체 블록들이 재배열 될 수 있는 경우를 구하기 위해 순열을 이용할 수 있다.

Problem

Given : 7 이하의 양의 정수

output : n 길이를 가진 순열(순서는 중요하지 않음)

 

예제 데이터와 결과

Sample Dataset

3

Samplpe output

6 # 순열의 개수 : n
1 2 3  # 순열 예시 (순서는 상관없음)
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

- 3*2*1 = 6

- 만약 n = 7이라면, length는 7*6*5*4*3*2*1 = 5040개

 

순열이란 

 

• 서로 다른 n개 중에서 r개를 택하여 배열 : $_nP_r$
  • e.g.) 숫자 1,2,3,4,5로 세 자리 수를 만들 수 있는 수는?
    • 543 = $_5P_3$= 60가지
    • $_5P_3$ = $_5P_3$$\frac{54321}{2*1}$ = $\frac{5!}{2!}$
    • $_nP_r$ = $\frac{n!}{(n-r)!}$

---

패키지 사용

from itertools import permutations

n = 5
a = list(range(1,n+1))
a # [1, 2, 3, 4, 5]

permute = permutations(a,n)
print(list(permute))

재귀함수 사용

##  위 공식으로 보면 팩토리얼 구현 = 순열 구현 
Factorial(n):
    if(n > 1):
        return n * Factorial(n - 1)
    else:
        return 1

a = 3
print(Factorial(a))
# 6

## 특정 숫자를 제외하고 출력하는 방법
	# list의 합 이용 
	# n = 5,  List = [1,2,3,4,5]
	# 이떄, 0,1,2,3,4중에서 2 번째 수인 3 을 빼고 출력하고자 한다

List [i:] + List [i+1:] # [1, 2, 4, 5]

## permutation function 
def permut(list_n):
    n = len(list_n)
    
    if n == 1:
        return [list_n]
    else:
        out_list = []
        for i in range(n):
            
            inner_permuts = permut(list_n[:i] + list_n[i+1:])

            for inner_permut in inner_permuts:
                
                out_list.append([list_n[i]] + inner_permut)
                
        return out_list

## print output
n = 3
output = permut(list(range(1, n+1)))
llen = len(output)
print(llen)
for i in list(range(1,llen)) : 
    print(*output[i])

 

 

- 참고 : https://www.r-bloggers.com/2019/06/learning-r-permutations-and-combinations-with-base-r/

Learning R: Permutations and Combinations with base R | R-bloggers

 

파이썬이 잘 이해가 안가서 R코드로 먼저 이해하고 풀었다..ㅠ