파이썬 Combination, Permutation 구현

해당 내용은 코딩 테스트 합격자 되기의 저자께서 작성한 코드를 기반으로 작성했습니다.
출처

Combination

파이썬에서 조합은 itertools 라이브러리에 있는 combinations를 불러와 손쉽게 사용할 수 있다.

from itertools import combinations

def generate_combinations(arr, n):
    return list(combinations(arr, n))

arr = [1, 2, 3]
print(generate_combinations(arr, 2))

------------------------
[(1, 2), (1, 3), (2, 3)]

라이브러리를 사용하지 않고 구현하는 경우, 다음과 같이 코드를 작성한다.

def combinations(lst, r):
	result = []
    
    def generate_combination(chosen, remain, n):	
    	
        if n == 0:							# 원하는 r개의 원소를 선택한 경우
        	result.append(chosen[:])
        	return
        
        if not remain or len(remain) < n:	# 남은 원소 없거나, 선택 불가한 경우
        	return
        
        # 현재 원소를 선택하는 경우
        chosen.append(remain[0])
        generate_combination(chosen, remain[1:], n-1) 	# 재귀 호출
        chosen.pop()
        
        # 현재 원소를 선택하지 않는 경우
        generate_combination(chosen, remain[1:], n)		# 다음 원소
        
    generate_combination([], list, r)
    
    return result
lst = [1,2,3]
r = 2
print(combinations[lst, r])

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

Permutations

파이썬에서 순열은 Combinations와 함께 itertools에서 불러와 사용할 수 있다.

from itertools import permutations

def generate_permutations(arr):
    return list(permutations(arr))

arr = [1, 2, 3]
print(generate_permutations(arr)) 

------------------------------------------------------------------
[(1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1)]

라이브러리를 사용하지 않고 코드를 작성하는 경우 다음과 같이 작성할 수 있다.

def permutations(lst, r):
	result = []
    
    def generate_permutaion(chosen, remain):
    	
        if len(chosen) == r:
        	result.append(chosen[:])							# 만들어진 결과 추가
            return
            
        for i in range(len(remain)):
        	chosen.append(remain[i])							# 현재 원소 선택
            remaining_elements = remain[:i] + remain[i+1:]		# 현재 원소 제외
            generate_permutation(chosen, remaining_elements)	
            chosen.pop()										# 현재 원소 제거
    
    generate_permutation([], lst)
	
    return result
    
lst = [1,2,3]
r = 2
print(permutations(lst, r))