파이썬 permutations 구현 방법 - recursion

이번 포스팅에서는 순열과 조합중, 순열 함수를 직접 구현을 함께 해보겠습니다.
파이썬의 itertools 모듈에는 combinations, permutations함수가 이미 정의되어 있습니다.
이를 단순히 사용하기만 하는 것은 python.org등의 공식 문서를 참조하면 되기에 어렵지 않습니다.
하지만 순열의 정의, 우리가 일상속에서 그러하듯 그룹에서 그 부분집합을 추출하는 과정을 생각해보면 가능한  가능성을 코드로 쉽게 구현할 수 있습니다. 이번에는 간단하게 조합함수(combination)를 함께 구현해보겠습니다.

---

순열이란 무엇인가요?

순열의 정의를 함께 살펴보겠습니다.

Permutation - Wikipedia

nPr, n permutation r이라 읽습니다. 이는 서로 다른 n개의 대상 중 r 개를 골라 그 순서를 배열하는 경우의 수입니다.
저번 포스팅에서 이미 언급했듯이, nCr과는 다르게 선택된 대상의 순서 또한 고려해 경우의 수를 구하면 되겠습니다.

서로 다른 r개의 대상을 배열하는 방법의 수는 쉽게 알 수 있듯이 r!(r factorial)입니다. 그렇기 때문에 nPr의 경우는 
서로 다른 n개를 고른후, 그 r개를 배열하는 것이기 때문에, nCr x r! 로 경우의 수를 계산할 수 있습니다.

그렇다면 순서까지 고려한 가능한 모든 추출 결과는 어떻게 구할 수 있을까요?
위에서 언급한 combination과 permutation의 관계를 이용해서도 구할 수 있지만, 저희는 문제의 subproblem 으로 나누어 문제를 해결해보도록 하겠습니다.

 

---

예시 : 반장 선거

고등학교에서 자주 보는 순열 문제죠? 0번부터 4번까지 있는 학급이 있다고 생각해봅시다.
그리고 그 학급에서 회장, 부회장, 그리고 미화부장을 뽑아야 한다고 생각해봅시다. 이런 경우에는 뽑은 대상이 갖는 의미가 각각 다릅니다. 따라서, 우리는 이렇게 생각해볼 수 있겠습니다 : 

 

처음으로 뽑힌 사람은 회장, 그 다음으로 뽑힌 사람은 부회장, 마지막으로 뽑힌 사람은 미화부장으로 정한다.

 

그 모든 경우의 수는 그냥 explicit하게도 구할 수 있습니다. 하지만 우리는 subproblem으로 차근차근 해결해 보도록 하죠.

1. 회장 선출 : 

0번~ 4번의 학생중 누구나 회장이 될 수 있겠습니다. 이 중에서 우리는 일반성을 잃지 않고 2번의 학생이 회장이 되었다고 가정하겠습니다.

 

2. 부회장 선출 : 

이미 2번 학생이 선출되었으니, [0, 1, 3, 4]의 4명의 학생중 부회장, 미화부장을 마저 뽑으면 되겠습니다.
이는 일반성을 잃지 않고 4번 학생이 부회장으로 선출 되었다고 가정하겠습니다.

 

3. 미화부장 선출

2번 학생이 회장으로, 4번 학생이 부회장으로 선출되었으니 이제 [0, 1, 3]의 학생 중 미화부장을 마저 뽑으면 되겠습니다. 이렇게 1명만을 뽑을 경우의 수는 이제 우리가 눈에 보이게 구할 수 있겠죠? 

 

즉, 이렇게 생각해볼 수 있겠네요. 
0~4번의 5명의 학생들 중 3명에게 각각 서로 다른 직급을 할당하는 경우는
회장을 먼저 선출한 다음, 회장으로 선출되지 않은 나머지 4명의 학생들 중 2명에게 각각 서로 다른 직급을 할당하는 경우와 같
습니다.
 

네, 맞습니다. Recursive하게 문제를 해결할 수 있겠네요. 먼저 Recursion에 대해서 다시 상기해보고 가겠습니다.

---

Recall : Recursion

Recursion에 대해서도 저번 포스팅에서 다뤘습니다. Recursion이란 어떠한 함수를 호출할 때, 그 함수안에서 다시 자기 자신을 호출하는 것입니다. 그리고 Recursion을 이용하여 함수를 정의할 때에는
General case, 그리고 Base case로 나누어 정의해야 합니다.

 

General이란 말 그대로 한 함수 호출이 다른 함수 호출을 할 때에, 일반적으로 어떠한 조건을 변화시켜가며 호출을 하는지에 대한 정보가 서술되어 있습니다.

 

반대로 Base는 어떠한 지점에서 함수가 멈춰야 하는지가 서술되어 있습니다.

그럼 위의 예시에서 general, base case에 대해서 생각해봅시다.

---

General && Base

위의 기울여 쓴 곳, 밑줄 친 곳을 나누어 생각해볼까요? 밑줄친 기능을 하는 함수 pemutations를 생각해봅시다.

 

이 함수는 추출의 대상과 추출해야 할 대상의 수를 입력 받아, 그에 대한 모든 가능한 경우의 표본을 반환하는 함수로 정의 하겠습니다. 즉 permutations(population:list, num:int) -> list 의 형식이 되겠습니다.

 

permutations([0, 1, 2, 3, 4], 3) == ([0] + permutations([1, 2, 3, 4], 2)) + ([1] + permutations([0, 2, 3, 4], 2 )) + ([2] + permutations([2] + [0, 1, 3, 4], 2)) + ([3] + permutations([0, 1, 2, 4], 2)) + ([4] + permutations([0, 1, 2, 3], 2)) 

 

로 생각할 수 있겠죠?

---

 

마지막으로 추출할 대상의 수가 그 모집단의 크기보다 크다면 빈 리스트를 반환하고 작동을 멈춥니다.

permutations 구현하기 - general case

위에서 말했듯이, 우리는 base case에서 return을 통해 탈출해야 합니다. 따라서 반환할 값의 형태를 먼저 정하는 것이 좋겠습니다. 우리는 가능한 모든 결과를 담을 리스트를 반환할 것이므로, 이중 리스트를 반환하면 되겠습니다.

 

그러한 반환할 값을 담을 변수 ans를 함수가 호출될 때 정의하여 사용하면 되겠습니다.

 

이와같이 우리는 ans에 값을 담아가며 최종적으로 가장 처음 호출한 함수에서의 지역변수 ans에 원하는 정답이 담기게 되게끔 코드를 작성해야 합니다. 이를 위해서는 가장 기본적인 사항이지만, 일단 ans에 어떤 값이든 담겨 있어야 합니다. 그렇기 때문에 별도로 n == 1일 때에, 예외적으로 다르게 명령어를 적습니다.
각 원소에 대한 singleton을 ans변수에 담아가는 것입니다.

 

그 외의  1<n and n<len(ref)일 경우에는 위의 예시와 같이 구현하면 되겠습니다. 

permutations 구현하기 - base case

base case 는 n > len(ref)일 때입니다. 이 때 위에서 언급했듯이, 빈 리스트를 반환하며 탈출하면 되겠습니다.

 

permutations 구현하기 - 결론

위의 논리를 바탕으로 General과 Base를 구분하여 구현하였을 때, 아래와 같이 구현할 수 있겠습니다.

 

def permutations(ref, n):
    ## 우선, 결과를 담을 변수를 지정합니다. 이 변수는 이중 리스트를 담는 변수입니다.
    ans = []
    ## Base 
    if n > len(ref): return ans


    #General - (1)
    if n == 1:
        for item in ref: ans.append([item])
    #General - (2)
    elif n>1:
        for i in range(len(ref)):
            temp_ref = ref[:]
            temp_ref.remove(ref[i]) ## 순열의 정의에 따라 자유롭게 remove 메소드를 사용해도 되겠습니다.
            for p in permutations(temp_ref, n-1):
                ans.append([ref[i]]+p)
    return ans

if __name__ == '__main__':
    temp = permutations(list(range(5)), 3)
    for i, item in enumerate(temp):
        print(i, item)

 

 그 결과 출력은 아래와 같이 나오겠습니다.

0 [0, 1, 2]
1 [0, 1, 3]
2 [0, 1, 4]
3 [0, 2, 1]
4 [0, 2, 3]
5 [0, 2, 4]
6 [0, 3, 1]
7 [0, 3, 2]
8 [0, 3, 4]
9 [0, 4, 1]
10 [0, 4, 2]
11 [0, 4, 3]
12 [1, 0, 2]
13 [1, 0, 3]
14 [1, 0, 4]
15 [1, 2, 0]
16 [1, 2, 3]
17 [1, 2, 4]
18 [1, 3, 0]
19 [1, 3, 2]
20 [1, 3, 4]
21 [1, 4, 0]
22 [1, 4, 2]
23 [1, 4, 3]
24 [2, 0, 1]
25 [2, 0, 3]
26 [2, 0, 4]
27 [2, 1, 0]
28 [2, 1, 3]
29 [2, 1, 4]
30 [2, 3, 0]
31 [2, 3, 1]
32 [2, 3, 4]
33 [2, 4, 0]
34 [2, 4, 1]
35 [2, 4, 3]
36 [3, 0, 1]
37 [3, 0, 2]
38 [3, 0, 4]
39 [3, 1, 0]
40 [3, 1, 2]
41 [3, 1, 4]
42 [3, 2, 0]
43 [3, 2, 1]
44 [3, 2, 4]
45 [3, 4, 0]
46 [3, 4, 1]
47 [3, 4, 2]
48 [4, 0, 1]
49 [4, 0, 2]
50 [4, 0, 3]
51 [4, 1, 0]
52 [4, 1, 2]
53 [4, 1, 3]
54 [4, 2, 0]
55 [4, 2, 1]
56 [4, 2, 3]
57 [4, 3, 0]
58 [4, 3, 1]
59 [4, 3, 2]

---

이번 포스팅에서는 recursion과 permutation에 대해서 알아보았습니다.
permutation의 문제에 접근할 때 그 문제가 갖는 subproblem property를 잘 활용해 자연스럽게
recursion을 이용해 문제를 해결하였고, 그를 위해 general case, base case를 정의하였습니다.

 

다음 포스팅에서는 더 유익한 정보로 돌아오도록 하겠습니다. 감사합니다. 감사합니다.