조합과 순열이란?

1. 조합과 순열의 수학적 개념

• 순열(Permutation)
• 개의 원소 중에서 개의 원소들을 나열하는 경우의 수
• 공식으로 나타내면 로 나타낸다.
• 순열 시간 복잡도 상한치

• 조합(Combination)
• 개의 원소 중에서 개의 원소들을 고르는 경우의 수
• 공식으로 나타내면 로 나타낸다.
• 조합 시간 복잡도 상한치

2. 조합 알고리즘과 순열 알고리즘

• 순열 알고리즘
• 순열의 모든 경우를 살펴보는 알고리즘
순열 알고리즘 코드

N = 4
R = 3
lst = [1, 2, 3, 4]
check = [False] * N # 원소 사용 여부를 체크
# check[k] 가 true 이면 인덱스가 k인 원소가 사용중임을 나타냄.
# check[k] 가 false 이면 인덱스가 k인 원소가 사용중이지 않음을 나타냄.
choose = [] # 나열한 원소를 보관

def permutation(level):
	if level == R:
		# 나열한 R 개의 원소를 출력
		print(choose)
		return

	# for문
	for i in range(0, N):
		if check[i] == True: # 인덱스가 i인 원소가 이미 사용중이라면 continue
			continue

		choose.append(lst[i]) # 인덱스가 i인 원소를 선택(추가) 
		check[i] = True # 인덱스가 i인 원소를 사용하고 있으므로 true로 초기화

		permutation(level+1) # 다음 for 문으로 들어가는 역할

		check[i] = False # 인덱스가 i인 원소의 사용이 끝났으므로 false로 초기화
		choose.pop() # (넣었던) 인덱스가 i인 원소를 제거


permutation(0)

• 시간 복잡도:

• 조합 알고리즘
• 조합의 모든 경우를 살펴보는 알고리즘
조합 알고리즘 코드

N = 4
R = 3
lst = [1, 2, 3, 4]
choose = [] # 선택한 원소를 보관

def combination(index, level):
	if level == R:
		# 선택한 R 개의 원소를 출력
		print(choose)
		return

	# for문
	for i in range(index, N): 
		choose.append(lst[i]) # 인덱스가 i인 원소를 선택(추가)
		combination(i+1, level+1) # 다음 for 문으로 들어가는 역할
		choose.pop() # (넣었던) 인덱스가 i인 원소를 제거

combination(0, 0)

• 시간 복잡도:

3. 조합과 순열의 관계

• 과 의 차이점에 대하여

• 은 개 중에서 개를 고르는 경우의 수이다.

• 은 개 중에서 개를 나열하는 경우의 수이다.

• 을 개 중에서 개를 고른 후에 나열한다고 생각해보자.

그러면, 은 모든 경우에 대해 나열하면(순서를 바꾸면) 된다.

• 따라서, 이며, 이 수식을 정리하면 다음과 같다.