[Python] 순열과 조합 직접 구현하기 / itertools 사용하기

안녕하세요! daily_D 입니다! 👩🏻‍💻
오늘은 Python itertools 로 순열과 조합을 이용해보는 방법과
직접 구현하는 방법에 대해 알아볼까요?

---

➤ 순열 ( = permutations)

 : n 개의 원소에서 중복을 허용하지 않고 r개를 뽑아서 나열

• 직접구현

def permutations(array, r):
    for i in range(len(array)):
        if r == 1:
            yield [array[i]]
        else:
            for next in permutations(array[:i] + array[i+1:], r-1):
                yield [array[i]] + next

• itertools 사용

from itertools import permutations

for i in permutations([1, 2, 3, 4], 2):
    print(i, end=" ")
    
# 결과
# (1, 2) (1, 3) (1, 4) (2, 1) (2, 3) (2, 4) 
# (3, 1) (3, 2) (3, 4) (4, 1) (4, 2) (4, 3)

 

➤  중복순열 ( = product)

• itertools 사용

from itertools import product

for i in product([1, 2, 3], 'ab'):
    print(i, end=" ")
 
# 결과
# (1, 'a') (1, 'b') (2, 'a') (2, 'b') (3, 'a') (3, 'b')

 

➤  조합 ( = combinations)

: n 개의 원소에서 중복을 허용하지 않고 r개를 뽑음

• 직접구현

def combinations(array, r):
    for i in range(len(array)):
        if r == 1:
            yield [array[i]]
        else:
            for next in combinations(array[i+1:], r-1):
                yield [array[i]] + next

• itertools 사용

from itertools import combinations

for i in combinations([1, 2, 3, 4], 2):
    print(i, end=" ")
    
# 결과
# (1, 2) (1, 3) (1, 4) (2, 3) (2, 4) (3, 4)

 

➤  중복조합 ( = combinations with replacement)

• 직접구현

def combinations(array, r):
    for i in range(len(array)):
        if r == 1:
            yield [array[i]]
        else:
            for next in combinations(array[i:], r-1):
                yield [array[i]] + next

• itertools 사용

from itertools import combinations_with_replacement

for i in combinations_with_replacement([1, 2, 3, 4], 2):
    print(i, end=" ")
    
# 결과
# (1, 1) (1, 2) (1, 3) (1, 4) (2, 2) (2, 3) 
# (2, 4) (3, 3) (3, 4) (4, 4)