[SW 정글 9일차] 순열과 조합 사용하기

오늘은 알고리즘 문제를 풀면서 사용한 순열과 조합에 대해서 정리해보려고 한다.

문제를 보고 '아, 배열 안에 있는 수를 순서를 바꾼 모든 경우를 얻고 싶은데 어떻게 하지..'라는 생각을 가진 적이 많고 그 때마다 항상 인터넷 검색을 하고 순열을 쓰면 되는구나 혹은 조합을 쓰면 되는구나 했다.

오늘은 이렇게 글로 정리하면서 다음부터는 바로바로 떠올릴 수 있도록 해보고자 한다.

 

 

1. 순열 (permutation)

순열을 사용하는 경우는 어떠한 경우일까?

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

여기서 더 깊게 얘기하면 수학적인 개념을 얘기해야하므로 간단히 순열이 무엇인지만 얘기하고 넘어가겠다.

이러한 순열은 우리가 어떠한 배열을 가지고 있는데 그 배열에 있는 원소를 재배치하여 얻을 수 있는 모든 경우의 수를 얻고 싶을 때 사용할 수 있다.

물론, n개 중에 전부가 아닌 r개만 정하여 모든 경우의 수를 얻을 수도 있다.

 

 

그러면 순열을 얻기 위한 코드는 어떻게 될까?

순열을 구현하는 것은 재귀함수를 통해 아래와 같이 가능하다.

재귀함수 : 재귀의 의미(자기 자신을 호출하는 것)를 사용하여 자기 자신을 다시 호출하여 재참조하는 구조의 함수

# 재귀적으로 만들기
def perm(arr, depth, n, k):
    # depth가 0부터 시작하여 k라면 k개를 모두 뽑은 것이므로 print하고 return
    if (depth == k):
        print(arr)
        return
    for idx in range(depth, n):
        # 각 depth에 대해 남아 있는 것들 중에 모두 뽑아보고,
        # 해당 경우에 대해 재귀적으로 perm 함수를 돌리고,
        # 원상복구 하여 다시 경우의 수를 찾는다
        arr[idx], arr[depth] = arr[depth], arr[idx]
        perm(arr, depth+1, n, k)
        arr[idx], arr[depth] = arr[depth], arr[idx]

 

재귀함수 코드가 잘 이해가 안된다면 아래의 비재귀적인 선형함수를 참고해보자.

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

우리는 위에 제시된 2개의 코드로 순열을 구현할 수 있지만 파이썬에서는 굳이 직접 구현하지 않고 itertools 모듈에 있는 permutations를 import해서 쓰면 된다.

 

intertools 모듈의 permutations의 함수가 어떻게 짜져있는지 보면 아래와 같다.

def permutations(iterable, r=None):
    # permutations('ABCD', 2) --> AB AC AD BA BC BD CA CB CD DA DB DC
    # permutations(range(3)) --> 012 021 102 120 201 210
    pool = tuple(iterable)
    n = len(pool)
    r = n if r is None else r
    if r > n:
        return
    indices = list(range(n))
    cycles = list(range(n, n-r, -1))
    yield tuple(pool[i] for i in indices[:r])
    while n:
        for i in reversed(range(r)):
            cycles[i] -= 1
            if cycles[i] == 0:
                indices[i:] = indices[i+1:] + indices[i:i+1]
                cycles[i] = n - i
            else:
                j = cycles[i]
                indices[i], indices[-j] = indices[-j], indices[i]
                yield tuple(pool[i] for i in indices[:r])
                break
        else:
            return

사실 위의 코드까지 알아야할 필요가 있을까? 라는 생각을 가질 수 있지만 우리가 단순히 import해서 쓰는 permuations가 어떻게 코드로 구현됐는지 알고 넘어가면 좋을 것같다.

 

permutations는 매개값으로 2개의 변수를 받는데 하나는 우리가 순열을 만들고 싶은 interable object를 넣어주고 다른 하나는 순열의 길이를 넣어준다.

여기서, 순열의 길이를 설정하지 않으면 기본으로 interable object의 길이가 된다.

간단한 예제로 permutations의 결과를 봐보자.

import itertools
arr = [1, 2, 3, 4]
perm_arr = itertools.permutations(arr, 3)
print(perm_arr)
#결과 : <itertools.permutations object at 0x0000019651EFA1D0>
perm_arr = list(itertools.permutations(arr, 3))
print(perm_arr)
#결과 : [(1, 2, 3), (1, 2, 4), (1, 3, 2), (1, 3, 4), (1, 4, 2), (1, 4, 3),
# (2, 1, 3), (2, 1, 4), (2, 3, 1), (2, 3, 4), (2, 4, 1), (2, 4, 3), (3, 1, 2),
# (3, 1, 4), (3, 2, 1), (3, 2, 4), (3, 4, 1), (3, 4, 2), (4, 1, 2), (4, 1, 3),
# (4, 2, 1), (4, 2, 3), (4, 3, 1), (4, 3, 2)]

결과를 보면 itertools.permutations()를 하면 해당 데이터가 저장된 곳을 가리키는 주소가 반환이 되고

이것은 list(itertools.permutations())로 형변환을 해주면 우리가 원하는 순열 결과를 얻을 수 있다.

 

 

 

2. 조합 (Combination)

조합을 사용하는 경우는 어떠한 경우일까?

먼저 조합은 배열에서 서로 다른 n개의 원소 중에서 순서에 상관없이 r개를 선택하는 것을 말한다.

이러한 조합은 우리가 어떠한 배열을 가지고 있는데 그 배열에 있는 원소를 재배치하는데 (1, 3)과 (3, 1)은 같은 경우의 수로 취급하여 가능한 경우의 수를 얻고 싶을 때 사용한다.

물론, n개 중에 전부가 아닌 r개만 정하여 모든 경우의 수를 얻을 수도 있다.

 

 

그러면 조합을 얻기 위한 코드는 어떻게 될까?

조합을 구현한 코드는 아래와 같이 재귀함수로 가능하다.

def combination(array, r):
    chosen = []
    if r > len(array):
        return chosen

    if r == 1:
        for i in array:
            chosen.append(i)

    elif r > 1:
        # r 개 만큼 빼주는 이유 (순서가 고려사항이 아니기 때문에, r개는 고려하지 않아도 앞서서 정해진다)
        for i in range(len(array) - r + 1):
            for temp in combination(array[i + 1:], r - 1):
                chosen.append([array[i], temp])
    return chosen

 

조합도 순열처럼 반복문으로 구현이 가능하지만 우리가 배열의 원소 중에 선택한 갯수만큼 반복문을 돌리는 것이기에 코드의 모습만 봐도 그다지 좋은 방법이 아니라고 생각한다.

그래도 반복문으로 어떻게 구현이 가능한지 코드를 적어보면 다음과 같다.

아래 코드는 배열에서 3개의 원소를 골라 조합을 구하는 경우이다.

# arr이라는 배열이 있다고 가정

for i in range(len(number)):
    for j in range(i + 1, len(number)):
        for k in range(j + 1, len(number)):
            print(number[i], number[j], number[k])

 

위 코드 2개처럼 직접 조합을 구하기 위해 코드를 구현할 수 있지만 파이썬을 사용한다면 순열과 마찬가지로 itertools 모듈에서 Combinations라는 함수를 import해서 사용하면 된다.

Combinations 함수가 어떻게 구현됐는지 코드를 봐보자.

def combinations(iterable, r):
    # combinations('ABCD', 2) --> AB AC AD BC BD CD
    # combinations(range(4), 3) --> 012 013 023 123
    pool = tuple(iterable)
    n = len(pool)
    if r > n:
        return
    indices = list(range(r))
    yield tuple(pool[i] for i in indices)
    while True:
        for i in reversed(range(r)):
            if indices[i] != i + n - r:
                break
        else:
            return
        indices[i] += 1
        for j in range(i+1, r):
            indices[j] = indices[j-1] + 1
        yield tuple(pool[i] for i in indices)

순열과 마찬가지로 2개의 매개값을 받는데 순열은 r을 지정해주지 않으면 default value로 interable object의 길이를 갖지만 조합에서는 r을 반드시 지정해주어야한다.

r을 interable object의 길이와 똑같은 값을 준다면 interable object가 그대로 반환될 것이고 r보다 큰 값을 준다면 빈 배열이 반환이 된다.

그래서, 우리가 원하는 갯수를 r로 지정해주면 된다.

간단히 배열을 직접 넣어서 combinations의 결과를 확인해보자.

from itertools import combinations

arr = [1,2,3,4]

# list로 묶지 않고 결과를 받은 경우
print((combinations(arr, 3)))
#결과 : <itertools.combinations object at 0x00000224C8633A90>

# r이 배열의 길이보다 작은 경우
print(list(combinations(arr, 3)))
#결과 :[(1, 2, 3), (1, 2, 4), (1, 3, 4), (2, 3, 4)]


# r이 배열의 길이와 같은 경우
print(list(combinations(arr, 4)))
#결과 : [(1, 2, 3, 4)]


#r이 배열의 길이보다 큰 경우
print(list(combinations(arr, 5)))
#결과 : []

순열과 마찬가지로 combinations()를 그대로 출력하면 반환 값이 주소인 것을 알 수 있고 각각의 조합 경우의 수는 튜플형태로 반환된다.

 

 

순열과 조합을 제 때 이용하기 위해 공부했는데 다음부터는 이런게 필요해 할 때 바로바로 순열과 조합을 사용하게 되면 좋겠다.

---

어제 저녁부터 멀티 비타민과 오메가 3를 챙겨먹기 시작했다.

매일 새벽 2시 넘어서 기숙사에 가고 아침 7시 30분이면 기상을 하는 것을 반복하다보니 피로도가 확실히 느껴지기 시작했었다.

하지만, 오늘은 비타민과 오메가 3 덕분인지 몸이 무거운 느낌이 없고 정신이 맑은 느낌이 들었다.

앞으로 꾸준히 운동할 시간을 내기에는 힘드니까 먹는 것으로 건강을 챙겨야겠다.

 

나는 개인적으로 5개월이 굉장히 빠르게 갈 것같다는 느낌이 든다.

지금은 내가 정글에 들어오기 전에 흘려 공부했던 내용들을 깊이있게 공부하기 위해 시간을 투자하고 있다.

정말 내 것으로 만들기 위해.

나의 꾸준함과 성장가능성을 모두가 알아볼 수 있도록 하고 싶다.

그렇기 위해 오늘도 쉽게 잠에 들려하지 않고 내일 아침도 잠을 깨는 것에 힘들어 하지 않아야 한다.

그리고 깨어 있는 시간동안 최대의 효율을 내어 지식을 얻기 위해 노력해야한다.

 

---

<참고 자료>

https://gorakgarak.tistory.com/522?category=265216 

https://programmers.co.kr/learn/courses/4008/lessons/12836#note

https://docs.python.org/3/library/itertools.html

https://velog.io/@jwisgenius/%ED%8C%8C%EC%9D%B4%EC%8D%AC-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%88%9C%EC%97%B4%EA%B3%BC-%EC%A1%B0%ED%95%A9