순열 함수가 종료됐을 때 배열의 값을 다시 원상복구 해주어야 함 (그 다음 수와 다시 순열을 계산해야 하므로)
구현 주석으로 설명했으나, 제일 빠른건 직접 디버깅하면서 확인해보면 된다.
public static void swapPermutation(int[] arr, int depth, int n, int r) {
// depth와 r이 같으면 다 뽑았다는 것이므로
if (depth == r){
for(int i=0; i<r; i++){
System.out.print(arr[i] + " ");
}
System.out.println();
return;
}
else {
/*
1, 2, 3 세 개의 숫자를 순열로 구한다고 했을 때,
재귀의 특성 상
depth가 0일 경우 1XX, 2XX, 3XX을 구해야 함
depth가 1일 경우 12X, 13X 를 구해야 함
depth가 2일 경우 123, 132 를 구해야 함
depth == r에서 return 되면서 배열을 원상복구 시킨 후
depth가 0일 경우 2XX, 3XX 를 구하는 과정을 반복
*/
for(int i=depth; i<n; i++){
swap(arr, i, depth);
swapPermutation(arr, depth + 1, n, r);
swap(arr, i, depth);
}
}
}
public static void swap(int[] arr, int i, int j){
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
visited을 이용한 순열
방문했는지 확인할 수 있는 visited 배열과, 결과를 저장할 수 있는 result 배열이 필요함
Depth를 이용한 풀이
Depth와 r의 값이 같으면 모두 다 뽑았다는 것이므로 결과값 출력
visited를 통해 result에 데이터 저장 시 중복값이 들어가지 않도록 함
구현
public static void visitedPermutation(int[] arr, boolean[] visited, int[] result, int depth, int n, int r) {
if (depth == r){
for(int i : result){
System.out.print(i + " ");
}
System.out.println();
return;
}
else {
for(int i=0; i<n; i++){
if (!visited[i]){
visited[i] = true;
result[depth] = arr[i];
visitedPermutation(arr, visited, result, depth + 1, n, r);
visited[i] = false;
}
}
}
}
결과비교
결과를 살펴보면 아래와 같다.
swap을 이용한 순열과 visited를 이용한 순열의 데이터를 비교해보면,
swap에서는 3, 2, 1 / 3, 1, 2 순으로 출력이 되는데 visited에서는 3, 1, 2 / 3, 2, 1 순으로 출력이 된다.
따라서 swap을 이용해서 순열을 구했을 때는 순서대로 순열이 구해지지 않는다는 차이점을 발견할 수 있다.
