python - 순열 (permutaions), 조합 (combinations), 중복순열, 중복조합

python 을 이용하여 순열, 조합을 사용하여 문제를 해결할 때가 있다.

itertools 을 사용하면 간단하게 해결 가능하다.

직접 구현도 남기긴 하였지만 itertools 을 사용하여 간단히 해결하는게 깔끔하다.

순열

=> 반복 가능한 객체에 대해서 중복을 허용하지 않고 n개를 추출

=> 간단히 순서 의미있는 열

# 순열
from itertools import permutations

arr = [1,2,3,4]

print(list(permutations(arr, 3)))

 

중복순열

=> 반복 가능한 객체에 대해서 중복을 허용하고 n개를 추출

# 중복 순열
from itertools import product
arr = [1,2,3,4]
print(list(product(arr, repeat=3)))

 

순열 직접구현

# 재귀를 통한 순열 구현
def permutations(arr, n):
    result = []

    if n == 0:
        return [[]]
    
    for (i, num) in enumerate(arr):
        for j in permutations(arr[:i] + arr[i+1:], n-1):
            result.append([num] + j)
    return result
    
permutation = permutations([1,2,3,4], 3)
print(permutation)

 

 

조합

=> 반복 가능한 객체에 대해서 중복을 허용하지 않고 n개를 추출

=> 추출 순서 고려하지않음

# 조합
from itertools import combinations

arr = [1,2,3,4]

print(list(combinations(arr, 3)))

 

중복조합

=> 반복 가능한 객체에 대해서 중복을 허용하고 n개를 추출

# 중복 조합
from itertools import combinations_with_replacement
arr = [1,2,3,4]
print(list(combinations_with_replacement(arr, 3)))

 

조합 직접구현

# 재귀를 이용한 조합 구현
def combinations(arr, n):
    result = []

    if n == 0:
        return [[]]
    
    for (i, num) in enumerate(arr):
        for j in combinations(arr[i+1:], n-1):
            result.append([num] + j)
    return result
    
combination = combinations([1,2,3,4], 3)
print(combination)