순열
순열이란 서로 다른 n개의 값에서 r개를 뽑아 나열하는 수를 의미한다.
재귀함수를 이용한 순열 구현
순열은 재귀함수를 사용하여 구현할 수 있다. nCr (n개의 수 중에서 r개를 뽑아 나열하는 경우의 수)를 구현하기 전에 n개의 리스트에서 나열할 수 있는 모든 경우의 수를 구하는 코드를 먼저 작성해 보았다.
리스트에서 나열할 수 있는 모든 경우의 수 (순열)
순열은 주어진 n개의 수에서 수를 뽑아 줄을 세울 수 있는 모든 경우의 수를 의미한다. 같은 숫자가 있더라도 순서가 다르면 다른 경우의 수이다.
used 리스트를 만들어서 값을 뽑았는지 안 뽑았는지 체크해주고(0 : False, 1 : True) 수 하나를 뽑은 뒤 다음에 올 수 있는 모든 수를 반복문을 돌려 체크되지 않은 수를 넣고 -> 체크 -> 재귀 -> 빼고 -> 체크 해제를 반복한다.
input_list = [1,2,3,4,5] used = [0]*len(input_list) print(used) def perm(arr, n): if n == len(input_list): print(arr) return for i in range(len(input_list)): if not used[i]: used[i] = 1 arr.append(input_list[i]) perm(arr, n+1) arr.pop() used[i] = 0 perm([], 0)
리스트에서 뽑을 수 있는 모든 경우의 수 (조합)
나열할 수 있는 모든 경우의 수를 리스트에 저장하는 combi()라는 함수를 구현해 보았다. 주어진 리스트의 모든 원소들을 하나씩 넣고 재귀호출, 빼고 재귀호출을 하였다. 재귀함수의 탈출 조건은 주어진 리스트의 마지막 원소를 통과하는 시점, 하나씩 증가하는 값을 의미하는 파라미터 n의 값이 리스트의 길이와 같아지는 시점이다.
여기서, 시간을 많이 잡아 먹었던 구간이 있었다. 탈출 조건에서 ans의 값을 밖에서 정의한 answer_list에 append 하려 했는데, answer_list를 출력하면 빈값만 출력되는 것이었다.
global을 써보기도 하고 튜플같은 다른 자료형으로 써봤지만 풀리지 않았고, append 이전에 temp라는 다른 리스트에 ans의 값을 넣어주어 temp를 answer_list에 append하는 방식으로 해야 정상적으로 출력되었다.
nums = [1, 2, 3, 4, 5] answer_list = [] def combi(n, ans): if n == len(nums): temp = [i for i in ans] answer_list.append(temp) return ans.append(nums[n]) combi(n + 1, ans) ans.pop() combi(n + 1, ans) combi(0, []) print(answer_list)
nCr
다음은 주어진 리스트에서 r개의 값을 나열할 수 있는 경우의 수를 출력하는 함수를 구현해 보았다.
기본적인 구성은 위 코드랑 비슷하다. 인자에 r을 추가하여 탈출조건 내부에 길이가 r인 결과값만 리스트에 append 해주는 방식으로 nCr을 구현하였다.
nums = [1, 2, 3, 4, 5] answer_list = [] def nCr(n, ans, r): if n == len(nums): if len(ans) == r: temp = [i for i in ans] answer_list.append(temp) return ans.append(nums[n]) nCr(n + 1, ans, r) ans.pop() nCr(n + 1, ans, r) nCr(0, [], 3) print(answer_list)
파이썬 라이브러리
파이썬에는 permutaion과 combination을 쓸 수 있는 라이브러리를 제공한다.
순열(Permutations)
from itertools import combinations, permutations nums = [1,2,3,4] perm = list(combinations(nums, 2))[(1, 2), (1, 3), (1, 4), (2, 1), (2, 3), (2, 4), (3, 1), (3, 2), (3, 4), (4, 1), (4, 2), (4, 3)] 출력
조합(Combinations)
from itertools import combinations, permutations nums = [1,2,3,4] combi = list(combinations(nums, 2))
[(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)] 출력
문자열 리스트도 사용 가능.
순열, 조합으로 나온 원소들은 sum()을 사용하여 더하는 것도 가능하다.
굿.
※ 참고 1 : 순열, 조합을 잘 정리해놓은 블로그
※ 참고 2 : 순열, 조합을 파이썬으로 잘 구현한 블로그
