파이썬 알고리즘 (순열과 조합)

Jaewoong2·2021년 1월 28일

순열 알고리즘 조합 코딩테스트 파이썬

알고리즘공부

목록 보기

12/35

들어가기전에,

프로그래머스 완전 탐색 소수 찾기 문제를 풀면서 순열을 사용해야하는 것은 알았지만, 코드로 구현하기 가 어려워서 인터넷을 보며 참고 하고 공부한 사항을 정리

순열

nPr ==> n개의 순서를 고려해서 r개의 열 을 세우는 것.
선택 한 것이 r개가 될때 까지 반복(재귀) 하는 것이 중요하다.

def dfs_permutation(array, r):
    i_array = [(x, i) for i, x in enumerate(array)]
    stack = [[i] for _, i in i_array]
    return_list = []

    while len(stack) > 0:
        current = stack.pop()
        
        for i in range(len(i_array)):
            if i not in current:
                temp = current + [i_array[i][1]]
                if len(temp) == r:
                    elements = []
                    for idx in temp:
                        elements.append(i_array[idx][0])
                    return_list.extend([elements])
                else:
                    stack.append(temp)
    return return_list

print(dfs_permutation("ABCD", 2))

# > 출력
[['D', 'A'], ['D', 'B'], ['D', 'C'], ['C', 'A'], ['C', 'B'], ['C', 'D'], ['B', 'A'], ['B', 'C'], ['B', 'D'], ['A', 'B'], ['A', 'C'], ['A', 'D']]

"ABCD" 중 r개를 뽑는다고 생각 했을 때,
선택 한 것이 r개가 되게 하기 위하여

기준 을 제외한 나머지에서 r - 1 개가 뽑힐 때 까지 선택을 한다.

즉 , "ABCD" 에서 2개를 순열로 선택 하는 것은

0. '기준'을 뽑고, "나머지" 에서 `r - 1개` 를 선택 하는 것.
1. A를 뽑고, "BCD" 에서 1개를 순열로 선택하는 것
2. B를 뽑고, "ACD" 에서 1개를 순열로 선택하는 것
3. C를 뽑고, "ABD" 에서 1개를 순열로 선택하는 것
4. D를 뽑고, "ABC" 에서 1개를 순열로 선택하는 것

이 모든 4가지 경우의 수를 다 더한 것과 같은 것을 의미한다.

r-1 을 계속해서 하다 보면 최종적으로 1 이된다
이를 고려해서, 1 개씩 선택하며 r 개가 될 때까지 1개씩 선택한 것을 추가 하는 것으로 생각하면 된다

다시 위의 함수를 살펴보면, temp = current + [i_array[i][1]] 이 의미 하는 것을 하나 씩 살펴 보면,

1. current => 뽑아야 되는 갯수 r 이 될 때 까지 
나머지에서 1개씩 선택한 것들을 더한 것이다.

즉, 위에서 말한 과정을 계속해서 더한 현재 값
인 것이다.
(아직, r개 만큼 선택 되지 않음)

2. [i_array[i][1]] => 
전체에서 1개를 선택 했음을 의미한다.

3. temp => 현재값과 선택 된 값을 더한 것
즉, 미래의 값.

순열 재귀 함수

 def permutation(arr, r):
    arr = sorted(arr)
    used = [0 for _ in range(len(arr))]
    return_array = []
    def generate(chosen, used):
        # 내가 원하는 만큼 뽑았으면, return
        if len(chosen) == r:
            return_array.append(''.join(chosen))
            return

        for i in range(len(arr)):
            if not used[i]:
                chosen.append(arr[i])
                used[i] = 1
                generate(chosen, used)
                used[i] = 0
                chosen.pop()

    generate([], used)
    return return_array

위에서의 설명과 마찬가지로, r이 될 때까지 1개씩 더해주는 방법을 사용한다.

이 때, 재귀함수는 함수호출이 스택으로 쌓이기 때문에,

# stack         
| - | |  -  |  
| - | | a.b | 
| - | | a.c | 
| - | | a.d | 
| a | |  a  | 
| b | |  b  | 
| c | |  c  | 
| d | |  d  | 
 ----  -----

이런식으로 스택이 쌓이는데, A에서 호출된 함수에서 B가 chosen 에 들어 온 상태에서 generate() 함수를 실행하면, chosen 이 r 과 동일 함으로 , B가 chosen에 들어온 시점에서의 generate() 함수는 return_array 에 값을 저장하며 실행이 종료 되고,

B는 chosen 에서 빠지고, A가 들어 있는 상태에서 C가 chosen 으로 들어오게 된다.

이후 같은 방법으로 계속 되며

A.D 가 마지막으로 실행이 종료 되면 A가 들어 와있는 상태에서의 함수실행도 종료가 되며
B가 들어가며 또 B가 B.A B.C B.D 에서의 함수를 실행한다.

이렇게 스택에 값이 다 끝날 때 까지 순열을 한다.

조합

nCr n개 중에서 r개를 선택 하는 것. (순서 상관 없이)

0. '기준'을 뽑고, 한번이라도 선택 하지 않은 "나머지"
    에서 `r - 1개` 를 선택 하는 것 들을 합
1. A를 뽑고, "BCD" 에서 1개를 순열로 선택하는 것
2. B를 뽑고, "CD" 에서 1개를 순열로 선택하는 것
3. C를 뽑고, "D" 에서 1개를 순열로 선택하는 것
4. D를 뽑고, "" 에서 1개를 순열로 선택하는 것

1~4 의 과정들의 합 = 조합

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

print(combination("ABCD", 2))