파이썬 순열과 조합

표준 라이브러리

파이썬에서 순열과 조합을 사용하고 싶으면,
itertools 표준 라이브러리를 사용하면 됩니다.

 

순열은 itertools.permutations,
조합은 itertools.combinations입니다. 

 

https://comdoc.tistory.com/entry/%ED%8C%8C%EC%9D%B4%EC%8D%AC-from-itertools

[파이썬] from itertools

from itertools import permutations, combinations, combinations_with_replacement

a = 'abc'

for each in permutations(a):
    print(each)

# ('a', 'b', 'c')
# ('a', 'c', 'b')
# ('b', 'a', 'c')
# ('b', 'c', 'a')
# ('c', 'a', 'b')
# ('c', 'b', 'a')

for each in combinations(a, 2):
    print(each)

# ('a', 'b')
# ('a', 'c')
# ('b', 'c')

for each in combinations_with_replacement(a, 3):
    print(each)

# ('a', 'a', 'a')
# ('a', 'a', 'b')
# ('a', 'a', 'c')
# ('a', 'b', 'b')
# ('a', 'b', 'c')
# ('a', 'c', 'c')
# ('b', 'b', 'b')
# ('b', 'b', 'c')
# ('b', 'c', 'c')
# ('c', 'c', 'c')

import itertools


pool = [1, 2, 3]
print(list(itertools.permutations(pool)))
# [(1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1)]
print(list(itertools.permutations(pool, 2)))
# [(1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2)]
print(list(itertools.combinations(pool, 2)))
# [(1, 2), (1, 3), (2, 3)]
print(list(itertools.combinations_with_replacement(pool, 2)))
# [(1, 1), (1, 2), (1, 3), (2, 2), (2, 3), (3, 3)]

permutations와 combinations를 프린트하면
객체에 대한 정보만 출력됩니다.

pool = [1, 2, 3]
print(itertools.permutations(pool))
# <itertools.permutations object at 0x015E4210>

permutations와 combinations은
이터레이터 객체이기 때문입니다. 

이터레이터를
리스트나 튜플 등으로 변환해야
print 할 수 있습니다. 

혹시 이터레이터에 관심 있으신 분은 
https://docs.python.org/ko/3/library/itertools.html#module-itertools 
https://www.flowdas.com/blog/iterators-in-python/index.html 
등을 참고하시기 바랍니다. 

 

 

순열과 조합을 직접 만들어 보기(재귀)

 

가능한 모든 문자열 

'a', 'b', 'c'로
가능한 모든 문자열을
만들어 봅니다. 

 

3중 for 문을 돌리면...

for each1 in 'abc':
    for each2 in 'abc':
        for each3 in 'abc':
            print(each1 + each2 + each3)

# aaa
# aab
# aac
# aba
# abb
# abc
# aca
# acb
# acc
# baa
# bab
# bac
# bba
# bbb
# bbc
# bca
# bcb
# bcc
# caa
# cab
# cac
# cba
# cbb
# cbc
# cca
# ccb
# ccc

 

재귀

def recursive(result):
    if len(result) == 3:
        print(result)
        return
    for each in 'abc':
        recursive(result + each)


recursive('')

# aaa
# aab
# aac
# aba
# abb
# abc
# aca
# acb
# acc
# baa
# bab
# bac
# bba
# bbb
# bbc
# bca
# bcb
# bcc
# caa
# cab
# cac
# cba
# cbb
# cbc
# cca
# ccb
# ccc

 

재귀가 이해된다면,
다음 단계로....

 

재귀가 어렵다면,
파이썬의 표준 라이브러리들을 사랑합시다.

 

Life is too short, You need Python!

 

 

조합

 

여기서 중복을 막으면 어떻게 될까요?
조합이 됩니다.

 

방문 기록을 저장하는
visited set을 만들어
중복을 막았습니다.

 

조합의 정의를 생각해보세요. ^^
원소의 중복이 없고,
순서도 없죠(=무시하죠). 

 

위치를 불문하고
하나의 원소는
1개만 존재해야 합니다. 

def recursive(result, visited):
    if len(result) == 2:
        print(result)
        return
    for each in 'abc':
        if each not in visited:
            visited.add(each)
            recursive(result + each, visited)


recursive('', set())

# ab
# ac

조합은 파이썬 집합 자료형과 잘 어울리죠. 

def recursive(result, visited):
    if len(result) == 2:
        print(result)
        return
    for each in 'abc':
        if each not in visited:
            visited.add(each)
            recursive(result | {each}, visited)


recursive(set(), set())


{'b', 'a'}
{'c', 'a'}

 

순열

 

이제 중복을 살짝 열어봅시다. 

 

재귀함수에서 나온 뒤 
방문 기록을 삭제하면 
순열이 됩니다. 

 

'순'열은
원소의 중복이 없고,
'순'서가 있잖아요.
위치가 다를 수 있어요. 

def recursive(result, visited):
    if len(result) == 3:
        print(result)
        return
    for each in 'abc':
        if each not in visited:
            visited.add(each)
            recursive(result + each, visited)
            visited.remove(each)  # 순열~!


recursive('', set())

# abc
# acb
# bac
# bca
# cab
# cba

재귀로 순열 만들기 어렵지 않습니다. 

 

완벽히 이해되지 않더라도.

 

모든 숫자들의 조합에서
특정한 필터링을 거치면, 
조합과 순열이 나오는 군화. 

 

정도는 기억합시다. 

 

 

리스트로 순열을 만들어 보겠습니다. 

def recursive(result, visited):
    if len(result) == 3:
        print(result)
        return
    for each in ('a', 'b', 'c'):
        if each not in visited:
            visited.add(each)
            new_result = result.copy()
            new_result.append(each)
            recursive(new_result, visited)
            visited.remove(each)  # 순열~!


recursive([], set())

# ['a', 'b', 'c']
# ['a', 'c', 'b']
# ['b', 'a', 'c']
# ['b', 'c', 'a']
# ['c', 'a', 'b']
# ['c', 'b', 'a']

 

+ 연산자를 써서 간단하게 작성할 수도 있습니다. 

def recursive(result, visited):
    if len(result) == 3:
        print(result)
        return
    for each in ('a', 'b', 'c'):
        if each not in visited:
            visited.add(each)
            recursive(result + [each], visited)
            visited.remove(each)  # 순열~!


recursive([], set())

# ['a', 'b', 'c']
# ['a', 'c', 'b']
# ['b', 'a', 'c']
# ['b', 'c', 'a']
# ['c', 'a', 'b']
# ['c', 'b', 'a']

 

코드를 가다듬어 봅시다. 

 

여기까지로도 충분하지만, 
조금 더 진도를 나가보겠습니다. 

 

Ture, False로 구성된 list로
방문 체크를 합니다. 

visited set에 객체를 넣고 빼는 것보다 빠릅니다. 

elements = ('a', 'b', 'c')


def recursive(result, visited):
    if len(result) == 3:
        print(result)
        return
    for i, each in enumerate(elements):
        if visited[i] is False:
            visited[i] = True
            recursive(result + [each], visited)
            visited[i] = False


recursive([], [False] * len(elements))

 

범용적으로 작동하도록 작성한다면...

def recursive(result, visited, elements, n):
    if len(result) == n:
        print(result)
        return
    for i, each in enumerate(elements):
        if visited[i] is False:
            visited[i] = True
            recursive(result + [each], visited, elements, n)
            visited[i] = False


def permutations(elements, n):
    recursive([], [False] * len(a), elements, n)


a = ('a', 'b', 'c')
permutations(a, 3)
print('---------')
permutations(a, 2)
print('---------')
permutations(a, 1)

 

좀 더 파이썬스럽게 고친다면..

 

파이썬은 
함수 내에서 함수 선언이 가능합니다. 

 

바깥 함수의 지역 변수(elements와 n)는
안쪽 함수(recursive)에서 전역 변수처럼 사용할 수 있습니다.

 

이렇게 수정하면,
인자로 전달되는 변수를 줄일 수 있어
코드가 깔끔해집니다. 

def permutations(elements, n):
    def recursive(result, visited):
        if len(result) == n:
            print(result)
            return
        for i, each in enumerate(elements):
            if visited[i] is False:
                visited[i] = True
                recursive(result + [each], visited)
                visited[i] = False

    recursive([], [False] * len(a))


a = ('a', 'b', 'c')
permutations(a, 2)

바깥 함수의 지역 변수를
안쪽 함수에서 읽을 때는 별다른 제한이 없습니다.

 

하지만,
안쪽 함수에서
바깥 함수의 지역 변수에 쓰기를 할 때는
nonlocal을 선언해 주어야 합니다.

 

전역 변수를 읽을 때는 별 제한이 없고,
전역 변수에 뭔가를 쓸 때는
global 선언이 필요한 것과 같습니다. 

 

전역 변수는 코드가 복잡해졌을 때
변수의 값을 어디서 바꾸는지 알기가 힘듭니다.
그래서 전역 변수는 가급적이면 사용하지 않습니다. 

 

전역 변수가 쓰면 좋은 상황일 때,
이렇게 처리합니다.  

 

객체 지향적인 방법론으론
클래스로 한 번 싸주어,
클래스 변수(정적 변수)나, 인스턴스 변수로
처리할 수 있습니다.

 

파이썬은 객체지향도 가능하지만,
함수 내 함수도 선언할 수 있기 때문에,
함수를 함수로 한 번 싸 주어
전역 변수를 로컬 변수로 만드는 방법도 
가능합니다.  

 

 

result의 길이를 고정하는 방식입니다. 

 

len(result)로 완성 여부를 알 수 없기 때문에, 
counter 변수를 만들어 완성된 문자열의 길이를 기록합니다. 

 

재귀를 반복할 때마다
새 리스트(복사본)를 만들지 않고, 
하나의 리스트에 쓰기를 반복하기 때문에 
메모리 효율과 속도면에서 더 뛰어납니다.  

def permutations(elements, n):
    def recursive(result, visited, counter):
        if counter == n:
            print(result)
            return
        for i, each in enumerate(elements):
            if visited[i] is False:
                visited[i] = True
                result[counter] = each
                recursive(result, visited, counter + 1)
                visited[i] = False

    recursive([''] * n, [False] * len(a), 0)


a = ('a', 'b', 'c')
permutations(a, 2)

 

 

자리바꿈을 이용한 순열 알고리듬

구글에서 '순열 알고리즘'으로 검색하면 좋은 설명이 너무 많습니다. 

다들 아래와 같거나 유사한 그림을 그려 놓고 그 원리에 대한 설명을 할 겁니다. 
그림이 중요합니다.

출처 : https://www.geeksforgeeks.org/write-a-c-program-to-print-all-permutations-of-a-given-string/

 

 

 

그림을 보니 깊이 우선 탐색(DFS)과 비슷하죠? 
깊이 우선 탐색의 흐름을 따라 이해하시면 됩니다. 

 

코드는 그림과 비교하면서 한 줄 한 줄 보시면 됩니다. 
이해하면 인생이 편해집니다. 

def perm(arr, depth, length, end):
    if depth == end:
        print(arr[:end])
        return
    for i in range(depth, length):
        arr[i], arr[depth] = arr[depth], arr[i]
        perm(arr, depth + 1, length, end)
        arr[i], arr[depth] = arr[depth], arr[i]

length는 원소의 개수입니다. 
end는 최종 depth(= 출력할 원소의 개수)입니다. 

 

제가 노란 줄로 그어 놨는데 최종적으로 저런 순서의 출력물이 나옵니다.

 

만약 end = 2 즉 최종 뎁스를 2로 잡으면 2번째 줄인 ABC, BAC, CBA가 나오겠죠.. 
여기서 마지막 원소들(C, C, A)은 잘라 주면 됩니다. arr[:end]에 대한 설명 완료... 

 

for 문은 뎁스부터 length-1 까지 원소들을 swap 해주는데....
마지막 줄의 swap는 이전 뎁스의 순서로 돌리기 위한 swap입니다. 

 

핵심적인 부분은 모두 적어 두었고 코드도 어렵지 않습니다만, 
혹 부족한 부분이 있으시면 구글에서 순열 알고리즘으로 검색해서 상위 3개의 글을 정독하십시오.. 

perm([1, 2, 3], 0, 3, 3)

[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 2, 1]
[3, 1, 2]

perm([1, 2, 3], 0, 3, 2)

[1, 2]
[1, 3]
[2, 1]
[2, 3]
[3, 2]
[3, 1]

perm([1, 2, 3, 4], 0, 4, 4)

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

다른 언어에서 순열을 만드는 함수를 파이썬으로 수정해 보았습니다. 

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


print(permute([1,2,3]))

arr [:]으로 리스트의 얕은 복사(shallow copy)를 한다는 걸 잊지 맙시다. 

https://docs.python.org/ko/3/library/copy.html