순열(Permutation) 이론과 조합(Combination) 이론의 파이썬 구현

순열(Permutation)

 

순열(permutation)은 순서를 고려해서 선택한 경우의 수를 의미합니다.

 

from itertools import permutations

permutations(인자(반복 가능한 것 ex. 리스트, 문자열),뽑을 개수)

순열의 기본 구조입니다.

 

순열의 개수는 n! / (n-r)! 입니다.

 

1, 2, 3 숫자 3개가 있다고 할 때 순서를 고려해서 2장을 뽑으면 다음과 같습니다.
개수 : 3! / (3-2)! = 6 / 1 = 6
(1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2)

 

순서를 고려한다는 것은 (1, 2)와 (2, 1)를 다른 것으로 생각한다는 의미입니다.

 

from itertools import permutations

p=list(permutations([1, 2, 3], 2))

# 출력>>[(1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2)]
print(p)

a=[1,2,3]

for i in permutations(a):
    # 출력>>(1, 2, 3) (1, 3, 2) (2, 1, 3) (2, 3, 1) (3, 1, 2) (3, 2, 1)
    print(i,end=' ')
    
for i in permutations(a,2):
    # 출력>>(1, 2) (1, 3) (2, 1) (2, 3) (3, 1) (3, 2) 
    print(i,end=' ')

 

 

조합(Combination)

 

조합(combination)은 순서를 고려하지 않고 선택한 경우의 수를 의미합니다.

 

from itertools import combinations

combinations(인자(반복 가능한 것 ex. 리스트, 문자열),뽑을 개수)

조합의 기본 구조입니다.

 

조합의 개수는 n! / r! (n-r)! 입니다.

 

1, 2, 3 숫자 3개가 있다고 할 때 순서를 고려하지 않고 2장을 뽑으면 다음과 같습니다.
개수 : 3! / 2! (3-2)! = 6 * 2 = 3
(1, 2), (1, 3), (2, 3)

 

순서를 고려하지 않는다는 것은 (1, 2)와 (2, 1)를 같은 것으로 생각한다는 의미입니다.

 

from itertools import combinations

c=list(combinations([1, 2, 3], 2))

# 출력>>[(1, 2), (1, 3), (2, 3)]
print(c)

a=[1,2,3]
    
for i in combinations(a,2):
    # 출력>>(1, 2) (1, 3) (2, 3)  
    print(i,end=' ')

 

 

 중복 가능한 순열(product)

 

중복 가능한 순열은 product를 이용해 표현할 수 있습니다.

 

from itertools import product

product(인자(반복 가능한 것 ex. 리스트, 문자열), repeat)

중복 가능한 순열의 기본 구조입니다.

 

중복 가능한 순열의 개수는 n^r 입니다.

 

repeat라는 인자를 통해 앞의 인자를 반복해서 뽑는 기능입니다.

 

1,2,3 숫자 3개가 있다고 할 때 순서를 고려해서 2장을 뽑으면 다음과 같습니다.
개수 : 3^2 = 9
(1, 1), (1, 2), (1, 3), (2, 1), (2, 2), (2, 3), (3, 1), (3, 2), (3, 3)

 

from itertools import product

a=list(product([1, 2, 3], repeat=2))

# 출력>>[(1, 1), (1, 2), (1, 3), (2, 1), (2, 2), (2, 3), (3, 1), (3, 2), (3, 3)]
print(a)

 

 

 

 중복 가능한 조합(combinations_with_replacement)

 

중복 가능한 순열은 combinations_with_replacement를 이용해 표현할 수 있습니다.

 

from itertools import combinations_with_replacement

combinations_with_replacement(인자(반복 가능한 것 ex. 리스트, 문자열),뽑을 개수)

중복 가능한 조합의 기본 구조입니다.

 

중복 가능한 조합의 개수는 (n+r-1)! / r! / (n-1)!  입니다.

 

1,2,3 숫자 3개가 있다고 할 때 순서를 고려해서 2장을 뽑으면 다음과 같습니다.

개수 : (3+2-1)! / 2! / (3-1)! = 24 / 2 / 2 = 6 
(1, 1), (1, 2), (1, 3), (2, 2), (2, 3), (3, 3)

 

from itertools import combinations_with_replacement

a=list(combinations_with_replacement([1,2,3], 2))

# 출력>>[(1, 1), (1, 2), (1, 3), (2, 2), (2, 3), (3, 3)]
print(a)