[알고리즘] 순열과 조합

파이썬에서 순열과 조합을 구하기 위해 사용할 수 있는 3가지 함수가 있다.

from itertools import permutations
from itertools import combinations
from itertools import product

순열

permutations

서로 다른 n개의 원소에서 r개를 중복없이 골라 순서에 상관있게 나열하는 것을 순열이라고 한다.

사용 예시

items = [1, 2, 3, 4, 5]

from itertools import permutations
print(list(permutations(items, 2)))

#[(1, 2), (1, 3), (1, 4), (1, 5), (2, 1), (2, 3), (2, 4), (2, 5), (3, 1), (3, 2), (3, 4), (3, 5), (4, 1), (4, 2), (4, 3), (4, 5), (5, 1), (5, 2), (5, 3), (5, 4)]

조합

combinations

서로 다른 n개의 원소 중에서 순서에 상관없이 r개를 선택하는 것이다.

사용 예시

items = [1, 2, 3, 4, 5]

from itertools import combinations
print(list(combinations(items, 2)))

#[(1, 2), (1, 3), (1, 4), (1, 5), (2, 3), (2, 4), (2, 5), (3, 4), (3, 5), (4, 5)]

곱집합

product

곱집합이란 여러 집합들 간에 하나씩 뽑아 조합을 만들 수 있는 모든 수를 뜻한다.

사용 예시

items1 = [1, 2, 3, 4, 5]
items2 = ['a', 'b', 'c']

from itertools import product
print(list(product(items1, items2)))

#[(1, 'a'), (1, 'b'), (1, 'c'), (2, 'a'), (2, 'b'), (2, 'c'), (3, 'a'), (3, 'b'), (3, 'c'), (4, 'a'), (4, 'b'), (4, 'c'), (5, 'a'), (5, 'b'), (5, 'c')]

알고리즘

라이브러리를 사용하는 것도 좋지만, 알고리즘을 직접 구현해보는 것이 실력 향상에 도움이 될 것 같다.

재귀로 수열 구현하기

visited = []
res = []

def permutation(items, r, pos):
    if pos == r:
        print(res)
        return

    for item in items:
        if item not in visited:
            res.append(item)
            visited.append(item)
            permutation(items, r, pos+1)
            visited.pop()
            res.pop()

items = [1, 2, 3, 4, 5]
permutation(items, 2, 0)

######
[1, 2]
[1, 3]
[1, 4]
[1, 5]
[2, 1]
[2, 3]
[2, 4]
[2, 5]
[3, 1]
[3, 2]
[3, 4]
[3, 5]
[4, 1]
[4, 2]
[4, 3]
[4, 5]
[5, 1]
[5, 2]
[5, 3]
[5, 4]

위의 함수를 트리 형태로 표현하면 다음과 같다. 파란색으로 색칠된 부분은 visited에 있는 수로 호출되지 않았음을 의미한다.

재귀로 조합 구현하기

visited = []
res = []

def conbination(items, r, pos, index):
    if pos == r:
        print(res)
        return
    
    for item in items[index:]:
        if item not in visited:
            res.append(item)
            visited.append(item)
            conbination(items, r, pos+1, items.index(item))
            visited.pop()
            res.pop()

items = [1, 2, 3, 4, 5]
conbination(items, 2, 0, 0)

########
[1, 2]
[1, 3]
[1, 4]
[1, 5]
[2, 3]
[2, 4]
[2, 5]
[3, 4]
[3, 5]
[4, 5]

순열의 코드와 거의 일치하다.
하지만 조합은 순서를 고려하므로, 제한이 필요하다.

def conbination(items, r, pos, index):

argument 목록에 index를 추가한다. 이 index는 현재 기점이 되는 값이다.
예를 들면 [1, 2], [1, 3], [1, 4], [1, 5] 의 경우 1을 기점으로 뽑은 것 이고,

[2, 3], [2, 4], [2, 5] 의 경우엔 2를 기점으로 뽑은 것 이다.

여기서 2를 기점으로 삼을 경우엔 앞서 1이 포함된 모든 조합은 이미 선택했으므로 1 이외의 인덱스에서만 뽑으면 된다. 즉 리스트의 인덱스 2부터 탐색을 하면 된다. 따라서 다음과 같이 코드를 작성했다.

for item in items[index:]:
        if item not in visited: