[Algorithm] 조합론(combinatorics)

✨팩토리얼(factorial)

그 수보다 작거나 같은 모든 양의 정수의 곱

 

python 코드

import sys

n=int(sys.stdin.readline().rstrip())
su=1
for i in range(1,n+1,1): su*=i
sys.stdout.write(str(su))

 

 

 

 

 

✨순열(permutation)

순서가 부여된 임의의 집합을 다른 순서로 뒤섞는 연산
n개의 요소에서 k개를 뽑는다.

 

itertools의 permutations코드

from itertools import permutations

n=[1,2,3,4]
k=2

print("개수:"+str(len(list(permutations(n,k)))))
for i in permutations(n,k):print(i, end="")

#결과
#개수:12
#(1, 2)(1, 3)(1, 4)(2, 1)(2, 3)(2, 4)(3, 1)(3, 2)(3, 4)(4, 1)(4, 2)(4, 3)

 

 

 

 

 

 

 

 

 

 

✨조합(combination)

유한 개의 원소에서 주어진 수만큼의 원소들을 고르는 방법
조합의 수는 이항 계수로 주어진다.

 

python 코드

import sys
def factorial(a):
    sm=1
    for i in range(1,a+1,1): sm*=i
    return(sm)

N,K=map(int,sys.stdin.readline().rstrip().split(" "))

sys.stdout.write(str(int(factorial(N)/(factorial(K)*factorial(N-K)))))

 

 

 

itertools의 combinations 코드

from itertools import combinations

n=[1,2,3,4]
k=2

print("개수:"+str(len(list(combinations(n,k)))))
for i in combinations(n,k):print(i, end="")

#결과
#개수:6
#(1, 2)(1, 3)(1, 4)(2, 3)(2, 4)(3, 4)

 

 

 

 

 

 

 

 

 

🎈참고자료

https://ko.wikipedia.org/wiki/%EC%88%9C%EC%97%B4