Python으로 푸는 조합과 순열

arr = ['a', 'a', 'b', 'c']

순열 (permutation) :  원소의 값이 같더라도 순서가 다르면 서로 다른 원소로 취급하며, 

원소의 순서( [ ('a','b'), ('b','a) ] )가 다르면 서로 다른 경우의 수입니다.

순열 결과 : [('a', 'a'), ('a', 'b'), ('a', 'c'), ('a', 'a'), ('a', 'b'), ('a', 'c'), ('b', 'a'), ('b', 'a'), ('b', 'c'), ('c', 'a'), ('c', 'a'), ('c', 'b')]

ss

조합 (combination) : 원소들을 조합하여 만들 수 있는 경우의 수이며,

원소들의 값이 같으면 서로 같은 경우의 수입니다.

조합 결과 : [('a', 'a'), ('a', 'b'), ('a', 'c'), ('a', 'b'), ('a', 'c'), ('b', 'c')]

---

itertools를 사용하여 조합과 순열 구하기 

python에는 순열과 조합을 쉽게 구현할 수 있도록, itertools 라는 내장 라이브러리가 존재합니다. 

아래와 같이 몇줄의 코드로도 조합과 순열을 구할 수 있어요!

def combi():
    arr = ['a', 'a', 'b', 'c']
    print(list(itertools.permutations(arr, 2)))
    print(list(itertools.combinations(arr, 2)))
 
    # output
    # 순열(permutation)
    [('a', 'a'), ('a', 'b'), ('a', 'c'), ('a', 'a'), \
    ('a', 'b'), ('a', 'c'), ('b', 'a'),('b', 'a'), \
    ('b', 'c'), ('c', 'a'), ('c', 'a'), ('c', 'b')]
 
 
    # 조합(combination)
    [('a', 'a'), ('a', 'b'), ('a', 'c'), ('a', 'b'), ('a', 'c'), ('b', 'c')]

재귀로 조합 구하기

itertools를 이용해서인지, 그 이유는 정확히 모르겠지만, 재귀로 문제를 풀 경우에는 시간 초과 없이 문제를 해결하는 경우도 있습니다. 

그래서 재귀로 조합을 구하는 방법을 구현해 보았습니다. 순열과 조합을 구할때는 리스트의 크기가 클 수록 연산 속도가 매우 느리기 때문에 itertools를 사용해서 문제를 풀다보면 시간 초과가 나기도 합니다.

분명히 intertools의 generator 객체의 속성을 이용해서 풀었는데도 말이에요. (이해가 아직도 안가요..)

그래서 재귀로 함수를 구현하는 방법을 아래에 정리해보고자 합니다.

n = 2, m = 3인 2차원 배열은 아래처럼 탐색하도록 할게요.

# 6개의 원소가 있는 2차원 배열 탐색
for i in range(0, n * m):
    x = i // 3
    y = i % 3
    print((x, y))
 
# output
(0, 0)
(0, 1)
(0, 2)
(1, 0)
(1, 1)
(1, 2)
 

재귀와 itertools로 2차원 배열에서 N개 만큼의 원소 선택하기

2차원 배열에서 N개만큼의 원소를 선택하는 코드를 구현할 수 있습니다. 

아래의 코드를 이해하게되면, 백준의 <연구소> 문제를 푸는데 훨씬 수월할 수 있습니다.

유사한 문제의 기본이 되는 구조이므로, 잘 이해해두는게 중요합니다.

백준의 <연구소> 문제 풀이 보러 가기

import itertools
import copy
 
arr = [[0,0],[0,0]]
 
def combi():
    arr = ['a', 'a', 'b', 'c']
    print(list(itertools.permutations(arr, 2)))
    print(list(itertools.combinations(arr, 2)))
    # 순열(permutation)
    #[('a', 'a'), ('a', 'b'), ('a', 'c'), ('a', 'a'), ('a', 'b'), ('a', 'c'),\
    # ('b', 'a'), ('b', 'a'), ('b', 'c'), ('c', 'a'), ('c', 'a'), ('c', 'b')]
 
    # 조합(combination)
    # [('a', 'a'), ('a', 'b'), ('a', 'c'), ('a', 'b'), ('a', 'c'), ('b', 'c')]
 
 
# itertools를 활용한 구현
def itertoolsSetOne():
    posList = []
 
    # 모든 원소를 담은 리스트를 생성
    for i in range(0, 2*2):
        posList.append((i//2, i%2))
 
    # itertools를 활용하여 조합 구하기
    for pos1, pos2, pos3 in itertools.combinations(posList, 3):
        temp = copy.deepcopy(arr)
        temp[pos1[0]][pos1[1]] = 1
        temp[pos2[0]][pos2[1]] = 1
        temp[pos3[0]][pos3[1]] = 1
 
        for j in range(0, 2):
            print(temp[j])
        print('\n')
 
 
# 재귀를 활용한 구현
def recursionSetOne(start, count):
    # 원소를 모두 골랐을 경우 출력
    if count == 0:
        for j in range(0, 2):
            print(arr[j])
        print('\n')
        return
 
    # n번째 원소부터 원소를 선택
    # n * m
    for i in range(start, 2*2):
        x = i // 2 # 2는 m
        y = i % 2 # 2는 m
 
        # 원소 선택
        arr[x][y] = 1
 
        # 나머지 배열의 원소들 중에서 count -1 만큼을 선택
        recursionSetOne(i+1, count - 1)
 
        # 선택한 원소를 초기화
        arr[x][y] = 0
 
 
if __name__ == "__main__":
    # 2차원 배열 arr에서 2가지 원소를 선택하여 1을 삽입하는 조합
    # start : 0, 갯수 : n
    recursionSetOne(0,3)
    itertoolsSetOne()
 
    # itertools를 활용한 순열과 조합
    combi()
 
"""
    # output
    [1, 1]
    [1, 0]
    
    [1, 1]
    [0, 1]
    
    [1, 0]
    [1, 1]

    [0, 1]
    [1, 1]
"""