[Python] 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)))

---

재귀

기본적인 아이디어는 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_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, []))