[Python] 순열, 조합 구현하기 - itertools & recursion

https://www.codeproject.com/Tips/1275693/Recursive-Permutations-in-Python

1. itertools를 이용한 방법

파이썬에 내장된 itertools패키지의 combinations모듈과 permutations모듈을 통해 손쉽게 순열과 조합을 구할 수 있다. 이때, 만들어진 순열과 조합은 튜플의 형태로 리스트에 담겨서 반환된다. -> ([(0, 1, 2), ...])

조합

from itertools import combinations

arr = [0, 1, 2, 3, 4, 5]

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

순열

from itertools import permutations

arr = [0, 1, 2, 3, 4, 5]

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

 

2. 재귀를 이용한 방법

재귀를 이용해서 조합과 순열을 구할 수 있다.

기본적인 아이디어는 다음과 같다. DFS, 백트래킹과 상당히 유사하다.

• combination([0,1,2,3], 2) = ([0],combination([1,2,3], 1)) + ([1],combination([2,3], 1)) + ([2],combination([3], 1)))
• permutation([0,1,2,3], 2) = ([0],permutation([1,2,3], 1)) + ([1],permutation([0,2,3], 1)) + ([2],permutation([0,1,3], 1))+ ([3],permutation([0,1,2], 1))

조합

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

    if n == 0: 
        return [[]]

    for i in range(0, len(arr)): 
        elem = arr[i] 
        rest_arr = arr[i + 1:] 
        for C in gen_combinations(rest_arr, n-1): 
            result.append([elem]+C) 
              
    return result

단순히 조합의 경우의 수를 구하고 싶은 경우, 다음의 코드를 이용할 수 있다.

def choose(n,k):
    if k == 0: 
       return 1
    elif n < k:
       return 0
    else:
        return choose(n-1, k-1) + choose(n-1, k)

print(choose(10,2))

순열

배열의 원소로 새로운 순열을 반환한다.

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

    if n == 0:
        return [[]]

    for i, elem in enumerate(arr): 
        for P in gen_permutations(arr[:i] + arr[i+1:], n-1):
            result += [[elem]+P]
              
    return result
    
    
arr = [0, 1, 2, 3, 4, 5]

print(gen_permutations(arr, 3))

배열의 인덱스로 새로운 순열을 만듦, 위 코드에 비해 좀 더 직관적이다.

def gen_permutation(n, depth, P):
    result = []
    if depth == n:
        return [P]
    else:
        for i in range(len(arr)):
            if chosen[i] == True:
                continue
            chosen[i] = True
            result += gen_permutation(n, depth+1, P+[i])
            chosen[i] = False
    return result


arr = [0, 1, 2, 3, 4]
chosen = [False for _ in range(len(arr))]

print(gen_permutation(3, 0, []))

 

 

참고

www.geeksforgeeks.org/combinations-in-python-without-using-itertools/

www.codeproject.com/Tips/1275693/Recursive-Permutations-in-Python

Algorithms with Python(신찬수 저)