순열과 조합

순열 : 순서를 고려하여 서로 다른 n개 중 r개 뽑기

$$ nPr = \frac{n!}{(n-r)!} $$

 

조합 : 순서를 고려하지 않고 서로 다른 n개 중 r 개 뽑기

 

$$ nCr = \frac{n!}{(n-r)!·r!} $$

 

파이썬에서는 itertools 모듈을 이용하여 순열과 조합을 쉽게 구할 수도 있다. 

인자로 뽑기를 할 리스트와 뽑을 개수를 넘겨주면 튜플 형태로 리스트에 담아서 반환해준다

// 순열
from itertools import permutations

lst=[1,2,3,4]
p_lst = permutations(lst, 2)

for el in p_lst:
    print(el, end=' ')
    
//결과
//(1, 2) (1, 3) (1, 4) (2, 1) (2, 3) (2, 4) (3, 1) (3, 2) (3, 4) (4, 1) (4, 2) (4, 3)

 

//조합
from itertools import combinations

lst=[1,2,3,4]
c_lst = combinations(lst, 2)

for el in c_lst:
    print(el, end=' ')
    
//결과
//(1, 2) (1, 3) (1, 4) (2, 3) (2, 4) (3, 4)

 

주어진 모듈을 사용하지 않고 구현을 한다면 다음과 같다

순열

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)

이미 뽑은 수들을 체크하기 위해 used 배열을 사용

generate 함수는 arr에서 하나씩 뽑아서 chosen에 append하고 used에 체크해놨다가 원하는 수(r)만큼 뽑으면 뽑은 수들을 출력하고 리턴

 

조합

def combination(arr, r):
    arr = sorted(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)):
            chosen.append(arr[nxt])
            generate(chosen)
            chosen.pop()
        
    generate([])

조합은 순서를 고려하지 않기 때문에 used 리스트가 필요없다 그냥 뽑은 위치 이전의 숫자들은 고려 안하고 뽑으면 된다

모양은 순열과 유사한데 단지 뽑는 위치가 chosen의 가장 마지막 원소의 arr에서의 인덱스 다음부터라는 점과 이미 뽑았던 수인지 체크하지 않는다는 점만 다르다