Intro

코딩테스트를 준비하다보면 아래의 경우를 고려하여 완전 탐색해야하는 문제를 쉽게 만날 수 있습니다. 

1) 서로 다른 N개중 순서를 생각하지 않고 M개를 선택하는 경우의 수

2) 서로 다른 N개중 순서를 생각하지 않고 중복을 허용하여 M개를 선택하는 경우의 수 

3) 서로 다른 N개중 순서를 생각하고 M개를 선택하는 경우의 수

4) 서로 다른 N개중 순서를 생각하고 중복을 허용하여 M를 선택하는 경우의 수

따라서, 위의 경우를 효율적으로 탐색하기 위해서 시간 복잡도와 모듈을 활용한 탐색 방법을 정리해 두려고 합니다.

저는 주로 python3를 사용하여 ps하기 때문에 itertools 패키지 사용법과 함께 정리하겠습니다.

위의 경우를 순서대로 알아보겠습니다.

1) 조합 (combiantions)

시간복잡도: nCr = n!/(n-r)!r!

from itertools import combinations

nums = [1,2,3]
for i in range(1, len(nums)+1):
	print(list(combinations(nums,i)))
    
# [(1,), (2,), (3,)]
# [(1, 2), (1, 3), (2, 3)]
# [(1, 2, 3)]

2) 중복 조합

시간복잡도: nHr=n+r−1Cr = (n+r-1)! / r!

from itertools import combinations_with_replacement

nums = [1,2,3]
for i in range(1, len(nums)):
	print(list(combinations_with_replacement(nums, i)))
    
# [(1,), (2,), (3,)]
# [(1, 1), (1, 2), (1, 3), (2, 2), (2, 3), (3, 3)]

3) 순열

시간복잡도: nPr = n!/(n-r)!

from itertools import permutations

nums = [1,2,3]
for i in range(1, len(nums)):
	print(list(permutations(nums, i)))
    
# [(1,), (2,), (3,)]
# [(1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2)]

4) 중복 순열

시간복잡도: n∏r = n^r

from itertools import product

nums = [1,2,3]
for i in range(1, len(nums)):
	print(list(product(nums, repeat = i)))
    
# [(1,), (2,), (3,)]
# [(1, 1), (1, 2), (1, 3),(2, 1), (2, 2), (2, 3),(3, 1), (3, 2), (3, 3)]

순열(permutations)

서로 다른 n개의 원소에서 r개를 중복없이 골라 순서대로 나열하는 경우의 수

순열 구현

def permutation(arr,r):
    arr = sorted(arr)
    used = [0 for _ in range(len(arr))]

    def generate(chosen, used):
        if len(chosen) == r:
            print(chosen)
            return

        for i in range(len(arr)):
            if not used[i]:
                chosen.append(arr[i])
                used[i] = 1
                generate(chosen, used)
                used[i] = 0
                chosen.pop()

    generate([],used)

조합(Combinations)

서로 다른 n개의 원소에서 r개를 뽑는 경우의 수

조합 구현

def combination(arr, r):
    arr = sorted(arr)
    used = [0 for _ in range(len(arr))]

    def generate(chosen):
        if len(chosen) == r:
            print(chosen)
            return

        start = arr.index(chosen[-1]) + 1 if chosen else 0
        for nxt in range(start, len(arr)):
            if used[nxt] == 0 and (nxt == 0 or arr[nxt-1] != arr[nxt] or used[nxt-1]):
                chosen.append(arr[nxt])
                used[nxt] = 1
                generate(chosen)
                chosen.pop()
                used[nxt] = 0
    generate([])

순열, 조합 파이썬 라이브러리

itertools

import itertools
pool = ['A','B','C']
print(list(map("".join, itertools.permutaions(pool, 2)))) # 순열
print(list(map("".join, itertools.combinations(pool, 2)))) # 조합

참고

• https://velog.io/@yeseolee/python%EC%9C%BC%EB%A1%9C-%EC%88%9C%EC%97%B4%EA%B3%BC-%EC%A1%B0%ED%95%A9-%EC%A7%81%EC%A0%91-%EA%B5%AC%ED%98%84%ED%95%98%EA%B8%B0