Python 조합과 순열 라이브러리 없이 구현하는 방법 + 라이브러리 itertools

조합과 순열을 백트래킹을 이용해 구현할 수 있다. 파이썬에 라이브러리를 사용할 수 있지만 코딩테스트에 백트래킹 문제를 대비하기 위해서는 조합, 순열을 직접 구현해 보는 것이 도움이 될 것 같다.

 

 

1️⃣ 조합

---

def comb(arr,n):
    result = []

    def backtrack(start,comb): # comb 리스트
        if len(comb) == n: # 종료식
            result.append(list(comb))
            return
        for i in range(start,len(arr)):
            comb.append(arr[i])
            backtrack(i+1,comb)
            comb.pop() # 마지막 인덱스를 꺼냄
    
    backtrack(0,[])
    return result
    
print(comb([1,2,3,4],2))

 

 

2️⃣ 순열

---

# 순열 라이브러리 없이 구현
def perm(arr):
    result = []
    def backtrack(start):
        if start == len(arr):
            result.append(arr[:])
            return
        for i in range(start, len(arr)):
            arr[start], arr[i] = arr[i], arr[start] # 스왑을 통해 원소의 위치를 변경 
            backtrack(start + 1)
            arr[start],arr[i] = arr[i], arr[start] # 백트래킹을 나오면 바뀐 위치를 이전 상태로 복구
    backtrack(0)
    return result

print(perm([1,2,3]))

 

3️⃣ 내장함수 이용

---

 1. 조합 라이브러리 itertools.combination(조합을 생성할 iterable 객체, 크기)

import itertools

data = [1, 2, 3]

for i in itertools.combination(data, 3):
    print(list(i), end=' ')

 

 

2. 순열 라이브러리 itertools.permutations(순열을 생성할 iterable 객체, 크기)

import itertools

data = [1, 2]

for i in itertools.permutations(data, 2):
    print(list(i), end= ' ')