Algorithm. 백트래킹 - 순열

1. 순열

• 예시) 원소 개수 n = 4 -> 집합 = {A, B, C, D}, 4!인 24가지의 경우가 존재
  • 따라서 상태 공간 트리에서의 단말노드의 수는 24개이다.
  • 24개의 후보해가 존재한다는 것이고 이것은 단말노드의 수와 같다.

• 노드 방문 시마다 원소를 가리키는 인덱스 값을 저장
• 같은 원소 수를 갖는 부분집합과 순열의 상태 공간 트리의 높이는 같다.
• 순열의 경우 높이가 다른 노드는 선택지 수가 동일하지 않다.
  • 선택할 때마다 다음 선택의 선택지 수가 하나씩 줄어든다.

소스코드

# order[] : 순열의 순서를 저장하는 리스트

def permutation(order, k, n):
    if k == n: # 다 선택하면
    	print_order_array(order, n): # 출력
    else:
    	check = [False] * n # 어떤 선택을 했는지 조사
        for i in range(k):
             check[order[i]] = True # 선택된 값에 대해서 체크
        
        for i in range(n):
            if check[i] == False: # 선택 안된 값에 대해서
            	order[k] = i # order 리스트에 저장
                permutation(order, k+1, n) # 재귀 호출