Python 순열, 조합 구현하기

파이썬은 itertools 패키지를 통하여 순열과 조합 기능을 제공한다. 

 

itertools를 이용한 순열과 조합 사용 방법은 아래와 같다. 

 

from itertools import combinations, permutations



arr = [1,2,3,4]



print(list(combination(arr, 2)))

print(list(permutations(arr,2)))

 

하지만 내장된 순열과 조합 기능을 사용할 수 없는 경우(i.e. 코딩 테스트)도 있기 때문에

직접 순열과 조합 기능을 구현하여 사용할 줄 알아야 한다. 

 

직접 구현하는 경우 성는 자체를 올리는 것보다 발상을 이해하여 추후 다시 사용할 수 있도록 간편하는 것이 중요하다고 생각하여 아래와 같이 구현하였다. 

 

아마도 성능 자체는 높지 않으나, 기억하기는 쉬울 것 같다. 

 

def combination(arr, n):
    result = []
    if n == 0:
        return [[]]
    if n == 1:
        result = [[i] for i in arr]
        return result
    for i in range(len(arr)):
        elem = arr[i]
        c = combination(arr[i+1:], n-1)
        for rest in c:
            result.append([elem]+rest)
    return result


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


data = [1, 2, 3, 4]
print(permutation(data, 2))
print(combination(data, 2))

 

각각에 대해서 자신을 제외한 서브 행렬에 대하여 값을 더하면 순열과 조합이 나오는 것이다. 

 

추가로 조합의 경우에는 순회 할 때 자신 앞의 데이터를 선택하면 중복이므로 고려하지 않는 것이 특징으로

 

위의 두 함수는 실제 구현 상 1줄 (arr[:i]) 만이 차이나게 된다.