[Algorithm/Python] 파이썬 itertools에서 combinations, permutations를 사용하지 않고, 조합과 순열 구현

파이썬에서는 순열과 조합을 간단하게 바로 구해볼 수 있다.
그러나, itertools가 기억이 나지 않는 경우를 대비하여 순열과 조합을 직접 구현해보도록 하자.
 

📌 itertools 패키지의 combinations, permutations 활용

먼저 itertools를 통해 조합과 순열을 구하는 방법이다.

✅ [ CODE ]

# 조합
from itertools import combinations

arr = [0, 1, 2, 3]
print(list(combinations(arr, 2))) # [(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3)]

✅ [ CODE ]

from itertools import permutations

arr = [0, 1, 2]
print(list(permutations(arr, 3))) # [(0, 1, 2), (0, 2, 1), (1, 0, 2), (1, 2, 0), (2, 0, 1), (2, 1, 0)]

 

📌 재귀함수를 이용한 조합과 순열 구현

combinations([0, 1, 2, 3], 2)
= [0] + combinations([1, 2, 3], 1)
+ [1] + combinations([2, 3], 1)
+ [2] + combinations([3], 1) 로 표현할 수 있다.

✅ [ CODE ]

# 조합
def combinations(arr, n):
    result = []
    if n == 0:
        return [[]]

    for i in range(len(arr)):
        p = arr[i]
        for j in combinations(arr[i + 1:], n - 1):
            result.append([p] + j)

    return result

arr = [0, 1, 2, 3]
print(combinations(arr, 2)) # [[0, 1], [0, 2], [0, 3], [1, 2], [1, 3], [2, 3]]

따라서, 맨 앞에 들어갈 arr[i] 뒷부분만 다시 combinations에 넣어주며, 재귀를 통해 모든 조합을 구할 수 있도록 한다.
 
permutations([0, 1, 2], 3)
= [0] + permutations([1, 2], 2)
+ [1] + permutations([0, 2], 2)
+ [2] + permutations([0, 1], 2) 로 표현할 수 있다.

✅ [ CODE ]

# 순열

def permutations(arr, n):
    result = []
    if n == 0:
        return [[]]
    
    for i in range(len(arr)):
        p = arr[i]
        for j in permutations(arr[:i] + arr[i + 1:], n - 1):
            result.append([p] + j)
    return result
    

arr = [0, 1, 2]
print(permutations(arr, 3)) # [[0, 1, 2], [0, 2, 1], [1, 0, 2], [1, 2, 0], [2, 0, 1], [2, 1, 0]]

따라서, 맨 앞에 들어갈 arr[i] 뒤에 arr[i]가 제외된 arr을 다시 permutations에 넣어주며, 재귀를 통해 모든 순열을 구할 수 있도록 한다.
 

📌 itertools 패키지의 combinations_with_replacement, product 활용

마지막으로 원소를 뽑을 때, 중복으로 뽑는 경우가 있다.
파이썬의 itertools를 이용하여 중복 조합과 중복 순열을 간단하게 구할 수 있다.

✅ [ CODE ]

# 중복 조합
from itertools import combinations_with_replacement

data = [0, 1, 2, 3]
result = list(combinations_with_replacement(data, 2))

#[(0, 0), (0, 1), (0, 2), (0, 3), (1, 1), (1, 2), (1, 3), (2, 2), (2, 3), (3, 3)]

 

✅ [ CODE ]

# 중복 순열
from itertools import product

data = [0, 1, 2]
result = list(product(data, repeat = 2)] 

# [(0, 0), (0, 1), (0, 2), (1, 0), (1, 1), (1, 2), (2, 0), (2, 1), (2, 2)]

repeat으로 개수를 지정해주는 부분만 조금 다르다.
 

📌 재귀함수를 이용한 중복 조합과 중복 순열 구현

combinations([0, 1, 2, 3], 2)
= [0] + combinations([0, 1, 2, 3], 1)
+ [1] + combinations([1, 2, 3], 1)
+ [2] + combinations([2, 3], 1) 로 표현할 수 있다.

✅ [ CODE ]

# 중복 조합
def combinations(arr, n):
    result = []
    if n == 0:
        return [[]]

    for i in range(len(arr)):
        p = arr[i]
        for j in combinations(arr[i:], n - 1):
            result.append([p] + j)

    return result

arr = [0, 1, 2, 3]
print(combinations(arr, 2)) 
# [[0, 0], [0, 1], [0, 2], [0, 3], [1, 1], [1, 2], [1, 3], [2, 2], [2, 3], [3, 3]]

 

permutations([0, 1, 2], 3)
= [0] + permutations([0, 1, 2], 2)
+ [1] + permutations([0, 1, 2], 2)
+ [2] + permutations([0, 1, 2], 2) 로 표현할 수 있다.

✅ [ CODE ]

# 중복 순열
def permutations(arr, n):
    result = []
    if n == 0:
        return [[]]
    
    for i in range(len(arr)):
        p = arr[i]
        for j in permutations(arr, n - 1):
            result.append([p] + j)
    return result
    

arr = [0, 1, 2]
print(permutations(arr, 2))
# [[0, 0], [0, 1], [0, 2], [1, 0], [1, 1], [1, 2], [2, 0], [2, 1], [2, 2]]