[Algorithm] Swap 방식 순열 구현

Permutation

전체 n개의 요소 중 r개의 요소를 뽑을 때, 순서를 생각하며 뽑는 방법의 수를 말한다.

뽑아낸 요소가 같아도 순서가 다르면 다른 것으로 생각을 한다.

간단하게 달리기 선착순을 생각하면 좋을것 같다.
전체 n명의 사람들 중 선착순 r명을 선택한다고 했을 때,

A, B, C순서로 들어온 경우와 A, C, B순서로 들어온 경우는 완전히 다르다고 할 수 있다.

여기서 사람들이 들어온 순서는 선택하는 경우의 수를 의미한다.

Swap을 이용한 Permutation

swap을 이용하여 순열을 구현하면, 따로 저장할 필요가 없어

$nPr$에서
$n$ : n
$r$ : r 일 때,

public void permutation(int[] arr, int n, int r, int depth) {
	if( depth == r){
    	// 마지막 요소까지 도달하였으므로 종료
        doSomething();
        return;
    }
    
    for(int i=depth; i<n; i++){
    	// 현재 인덱스와 인덱스 뒤의 요소를 스왑
    	swap(arr, depth, i);
        // depth를 한칸 이동시키고 스왑
        permutation(arr, n, r, depth+1);
        // 원래대로 돌림
        swap(arr, depth, i);
    }
}

public void swap(int[] arr, int idx, int idx2){
	int tmp = arr[idx];
	arr[idx] = arr[idx2];
	arr[idx2] = tmp;
}