[알고리즘] 순열과 중복순열, 조합과 중복조합 직접 구현하기 - 파이썬(python)

알고리즘 문제풀이를 하다보면 흔하게 볼 수 있는 순열과 조합 알고리즘에 대해 정리하려고 한다.

순열과 조합 문제는 완전탐색을 기본으로 하여 시간이 많이 걸리는 것이 단점이다. 따라서 소요시간을 줄이기 위해 백트래킹을 사용하기도 한다.

우선은 순열과 조합의 기본적인 개념에 대해 알아보자.

순열 (Permutation)

순열은 서로 다른 N개의 원소 중 R개를 뽑아서 중복 없이 순서를 고려하여 한줄로 나열하는 것을 말한다.

순열을 구하는 공식은 nPr = n x (n-1) x (n-2) x (n-3) x … x (n-r+1)로 나타낼 수 있다.

예를 들어 [1,2,3]을 순열로 나타낸다면 결과 값은 아래와 같다.

# 순열
1 2 3 / 1 3 2 / 2 1 3 / 2 3 1 / 3 1 2 / 3 2 1 /

이처럼 중복 없이 순서를 고려하여 만드는 것이다. 이러한 순열을 만드는 방법에는 여러가지가 있다.

순열에 필요한 만큼 for문과 조건 설정하기 : 가장 간단한 방법

# 순열의 대상이 되는 리스트
lst=[1,2,3]
# 몇자리의 순열을 구할지에 따라 for문의 횟수가 변경된다.
for i in range(3):
    for j in range(3):
        # 중복이 허용되지 않으므로 i와 j는 달라야 한다.
        if j !=i:
            for k in range(3):
                # k도 i,j와 달라야 한다.
                if k !=i and k != j:
                    print(lst[i],lst[j],lst[k], end = ' / ')

하지만 이 방법은 순열을 구할 대상이 커질수록 매우 비효율적이다. 따라서 보통은 재귀를 통해 순열을 구현한다.

재귀를 통한 순열 구현하기

# 순열의 대상이 되는 리스트
lst=[1,2,3]
# 순열을 만들떄 선택할 원소의 개수
N = 3
# 원소 선택 여부 확인 배열 
visit=[0]*N
# 원소를 넣을 배열
path=[0]*N

def perm(depth):
    # depth이 N에 도달하면 return
    if depth==N:
        print(*path, end=' / ')
        return
    # 리스트의 길이만큼 for문 실행
    for i in range(len(lst)):
        # 이미 방문한 곳이라면 지나친다.
        if visit[i]==1: continue
        # 아니라면 방문체크하고 자리에 원소를 채워준다.
        visit[i]=1
        path[depth]=lst[i]
        # 재귀함수를 호출하면서 깊이를 더해간다.
        perm(depth+1)
        # 돌아나오면서 방문배열 초기화
        visit[i]=0
perm(0)

# 1 2 3 / 1 3 2 / 2 1 3 / 2 3 1 / 3 1 2 / 3 2 1 /

파이썬 내장함수 itertools로 순열 구현하기

from itertools import permutations

lst = [1, 2, 3]
N = 3
print(list(permutations(lst, N)))

# 실행결과
# [(1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1)]

 

중복 순열

서로 다른 N개의 원소 중 R개를 뽑아서 중복을 허용하고 순서를 고려하여 한줄로 나열하는 것을 말한다.

순열과 중복순열의 차이는 이름에서 나타나듯이 중복 허용 여부이다.

따라서 [1,2,3]을 중복순열로 나타낸다면 결과값은 아래와 같다.

# 중복 순열
1 1 1 / 1 1 2 / 1 1 3 / 1 2 1 / 1 2 2 / 1 2 3 / 1 3 1 / 1 3 2 / 1 3 3 / 2 1 1 / 2 1 2 / 2 1 3 / 2 2 1 / 2 2 2 / 2 2 3 / 2 3 1 / 2 3 2 / 2 3 3 / 3 1 1 / 3 1 2 / 3 1 3 / 3 2 1 / 3 2 2 / 3 2 3 / 3 3 1 / 3 3 2 / 3 3 3 / 

재귀로 중복순열 구현하기

# 순열의 대상이 되는 리스트
lst=[1,2,3]
# 순열을 만들떄 선택할 원소의 개수
N = 3
# 원소를 넣을 배열
path=[0]*N

def perm(depth):
    # depth이 N에 도달하면 return
    if depth==N:
        print(*path, end=' / ')
        return
    # N만큼 for문 실행
    for i in range(N):
        # 자리에 원소를 채우기
        path[depth]=lst[i]
        # 재귀함수를 호출하면서 깊이를 더해간다.
        perm(depth+1)

perm(0)

# 1 1 1 / 1 1 2 / 1 1 3 / 1 2 1 / 1 2 2 / 1 2 3 / 1 3 1 / 1 3 2 / 1 3 3 / 2 1 1 / 2 1 2 / 2 1 3 / 2 2 1 / 2 2 2 / 2 2 3 / 2 3 1 / 2 3 2 / 2 3 3 / 3 1 1 / 3 1 2 / 3 1 3 / 3 2 1 / 3 2 2 / 3 2 3 / 3 3 1 / 3 3 2 / 3 3 3 /

순열과 다르게 방문여부를 체크할 필요가 없어 중복순열의 구현이 더 쉽다고 할 수 있다.

내장함수 itertools를 사용하여 중복순열 구현하기

from itertools import product

lst = [1, 2, 3]
N = 3
print(list(product(lst, repeat=3)))

# 실행결과
# [(1, 1, 1), (1, 1, 2), (1, 1, 3), (1, 2, 1), (1, 2, 2), (1, 2, 3), (1, 3, 1), (1, 3, 2), (1, 3, 3), (2, 1, 1), (2, 1, 2), (2, 1, 3), (2, 2, 1), (2, 2, 2), (2, 2, 3), (2, 3, 1), (2, 3, 2), (2, 3, 3), (3, 1, 1), (3, 1, 2), (3, 1, 3), (3, 2, 1), (3, 2, 2), (3, 2, 3), (3, 3, 1), (3, 3, 2), (3, 3, 3)]

 

조합(Combination)

조합은 서로 다른 원소 N개의 원소 중 R개를 중복이 없이 순서를 고려하지 않고 골라낸 것을 말한다.

조합을 구하는 공식은 nCr = (n x (n-1) x (n-2) x … x (n-r+1)) / (r x (r-1) x (r-2) x … x 2 x 1)로 나타낼 수 있다.

일반적으로 부분집합의 합을 구하는 문제에서 자주 사용된다.

재귀로 조합 구현하기

# 리스트에서 뽑을 원소의 개수
N=3
lst=[1,2,3,4]
# 조합을 저장할 배열
path=[0]*N

def comb(depth,start):
    if depth==N:
        print(path, end=', ')
        return
# 중복 허용이 불가능하지만 순열과 달리 방문배열이 필요하지 않다.
# start인자를 통해 이미 탐색이 완료된 부분은 버리고 탐색이 필요한 부분만 하면되기 때문이다.
    for i in range(start,len(lst)):
        path[depth]=lst[i]
        # 따라서 start는 현재 탐색한 곳 이후(i+1)부터라고 할 수 있다.
        comb(depth+1,i+1)

comb(0,0)

# 실행결과
# [1, 2, 3] [1, 2, 4] [1, 3, 4] [2, 3, 4]

내장함수 itertools로 조합 구현하기

from itertools import combinations

lst = [1, 2, 3, 4]
N = 3
print(list(combinations(lst, N)))

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

중복조합

중복조합은 서로 다른 원소 N개의 원소 중 R개를 중복을 허락하여 순서와 상관없이 골라낸 것을 말한다.

재귀로 중복조합 구현하기

# 리스트에서 뽑을 원소의 개수
N=3
lst=[1,2,3,4]
# 조합을 저장할 배열
path=[0]*N

def comb(depth,start):
    if depth==N:
        print(path, end=', ')
        return
# start인자를 통해 이미 탐색이 완료된 부분은 버리고 탐색이 필요한 부분만 검사하기
    for i in range(start,len(lst)):
        path[depth]=lst[i]
        # 중복이 허용되므로 조합과 달리 start는 현재 탐색한 곳(i)부터라고 할 수 있다.
        comb(depth+1,i)

comb(0,0)

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

내장함수 itertools로 중복조합 구현하기

from itertools import combinations_with_replacement

lst = [1, 2, 3, 4]
N = 3
print(list(combinations_with_replacement(lst, N)))

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

지금까지 순열, 중복순열, 조합, 중복조합에 대해서 알아보았다. 이를 구현하는 방법은 크게 재귀와 내장함수 itertools로 나눠진다. 따라서 문제에 따라 둘 중 하나를 선택하여 사용하면 될 것 같다.