순열과.조합. 무슨 말인지...알겠어요...? (feat. 순열과 조합 구현하기)

갑자기 고등학교 다닐 때 확률과 통계 선생님과 수학학원 선생님이 생각나서

 

두 분의 명언을 짬뽕해본 제목...

 

오늘 다룰 내용은 순열 조합 구현하기다 !!

 

BIG SPECIAL SHOUT OUT TO...

 

TIL: itertools 없이 순열과 조합

 

itertools 없이 순열과 조합을 구현해야하는 삼성 코테...

 

한번 같이 풀어뿌삐 해보자구요.

 

우선?

 

조합부터...

 

조합:

주어진 배열 array = [1,2,3,4] 가 있고, n = 2 가 있을 때

combinations([0,1,2,3], 2) = [[0] + combinations([1,2,3],1)] + [[1] + combinations([2,3],1)] + [[2] + combinations([3],1)]

 

def combinations(array,n):
	result = []
    # n이 0이면 빈 이중 배열 리턴
    if n == 0:
    	return [[]]
    # 그렇지 않으면
    for i in range(0, len(array)):
    	# 아까봤던대로 i번째 요소 빼주고
        elem = array[i]
        # 나머지요소만 사용해서
        rest = array[i+1:]
        # 모든 요소들에 대해 조합 진행
        for j in combination(rest,n-1):
        	result.append([elem]+j)
    return result

 

# itertools 쓴다면
from itertools import combinations

combs = list(combinations([1,2,3],2))
print(combs)
#[(1,2), (1,3), (2,3)]

 

 

그리고 순열 함 보실까요...?

 

순열과 조합의 한끝 차이는 바로 나머지 요소를 살짝만 twik하면 된다는 것 !!

 

왜냐면 순열은 그 앞의 것도 고려를 해야하기 때문

 

def permutations(array,n):
	# 초기 result 초기화
    result = []
    # 만약 n이 0이면
    if n == 0:
    	return [[]]
    # 그렇지 않으면 아까 진행했던 것 그대로 진행
    for i in range(len(array)):
    	# i 번째 요소 빼주고
        elem = array[i]
        # i를 제외한 모든 요소 더해줌
        rest = array[:i] + array[i+1:]
        # 모든 남은 요소들에 대해
        for P in permutations(array, n):
        	result += [[elem] + P]
            # 덧셈이 append와 같은 기능을 하려면
            # result.append([elem] + P) 도 가능 !!
    return result

 

# 다른 코테에서는 이 한 줄로 ~~
from itertools import permutations
perm = list(permutations([1,2,3],2))

print(perm)
# [(1,2), (1,3), (2,3), (2,1), (3,1), (3,2)]