순열과 조합

순열이란?

순열이란 순서를 정해서 나열하는 것을 말한다.

예를 들어 5명의 사람 중에 세 명을 뽑아 의자에 앉힌다고 가정한다. 그러면 첫 번째에는 5명의 사람 중 한 명이 앉을 수 있고, 두 번째에는 첫 번째에 앉은 사람을 제외한 4명의 사람이 앉을 수 있다. 이런 식으로 서로 다른 n개에서 r개를 택하여 일렬로 나열할 때, 나올 수 있는 경우의 수는 n(n-1)(n-2)···(n-r+1)이다.

파이썬에서는 for문을 통해서 순열을 구현할 수 있다.

def permute(arr):
    result = [arr[:]]
    c = [0] * len(arr)
    i = 0
    while i < len(arr):
        if c[i] < i:
            if i % 2 == 0:
                arr[0], arr[i] = arr[i], arr[0]
            else:
                arr[c[i]], arr[i] = arr[i], arr[c[i]]
            result.append(arr[:])
            c[i] += 1
            i = 0
        else:
            c[i] = 0
            i += 1
    return result

itertools.permutations를 사용하여 순열을 간단하게 구현할 수 있다.

import itertools
list(itertools.permutations(['1', '2', '3'], 2))

조합이란?

조합은 순열과 마찬가지로 n개에서 r개를 택하는데 순서가 중요하지 않은 경우이다.
예를 들면 과일 4개가 있는데 2개를 골라 바구니에 담는다고 가정한다. 담기만 하면 되므로 순서는 중요하지 않다. 딸기, 복숭아든 복숭아, 딸기든 똑같다. 이럴 경우에는 순열처럼 경우의 수를 계산하면 안된다. 조합일 경우에는 아래 식을 따른다.

파이썬에서는 for문을 통해서 조합을 구현할 수 있다.

lst = [1,2,3,4]
for i in range(len(lst)):
    for j in range(i+1, len(lst)):
        for k in range(j+1, len(lst)):
            print(lst[i], lst[j], [k])

itertools.combinations를 사용하여 조합을 간단하게 구현할 수 있다.

import itertools
list(itertools.combinations(['1', '2', '3', '4'], 3))

itertools 라이브러리를 사용하면 계산 속도가 빨라진다.