앞선 포스트에서 살펴봤듯이 순열을 구현하기 위해 필요한 개념은 3가지이다.
1. 순서대로 나열 - 반복문을 통해 순차적으로 접근한다.
2. 중복을 허용하지 않음 - 이미 사용한 요소가 무엇인지 저장해놓는다. 이를 위해 visited라는 이름의 배열을 사용한다.
3. 재귀를 통한 접근 - 선택해야할 요소들을 하나씩 줄여가면서 자신 호출
4개의 원소를 가진 배열을 만들고 여기서 3개를 선택해서 나열하는 경우의 수를 조사해보자.
private static char[] src = {'A', 'B', 'C', 'D'};
기본적인 코드의 흐름은 다음과 같다. 코드에 대한 설명은 주석으로 대체한다.
/**
* 순열을 만들고 출력하는 메서드
* @param r 선택할 요소의 개수
* @param current 현재 선택하는 요소의 index로 최대는 r-1
* @param temp 선택된 요소들이 저장될 배열
* @param visited 요소의 선택 상태를 저장할 배열
*/
private static void makePermutation(int r, int current , char [] temp, int [] visited) {
if(r==current) {// base part
// 완료된 상태이므로 배열 출력
}else { // inductive part
//사용되지 않은 요소를 찾아 사용 후 다음 호출
}
}
이제 내용을 채워보자.
/**
* 순열을 만들고 출력하는 메서드
*
* @param r 선택할 요소의 개수
* @param current 현재 선택하는 요소의 index로 최대는 r-1
* @param temp 선택된 요소들이 저장될 배열
* @param visited 요소의 선택 상태를 저장할 배열
*/
private static void makePermutation(int r, int current, char[] temp, int[] visited) {
if (r == current) {// base part
// 완료된 상태이므로 배열 출력
System.out.println(Arrays.toString(temp));
return;
} else { // inductive part
// 사용되지 않은 요소를 찾아 사용 후 다음 호출
for (int i = 0; i < src.length; i++) {
if (visited[i] == 0) {
visited[i] = 1; // 사용(방문) 표시
temp[current] = src[i]; // 사용
makePermutation(r, current + 1, temp, visited);
visited[i] = 0; // 다른 호출을 위해서 원상복구
}
}
}
}
위 과정에서 방문 표시를 위해 int[]을 사용했는데 방문여부만 표시할 계획이라면 true/false로 구성되는 boolean []도 당연히 괜찮다. 한걸음 더 나아가 자료의 총 개수가 32 이하라면 int를 이용하고 shift 연산으로 방문 여부를 처리할 수 있다.
다음 예를 살펴보자.
/**
* 순열을 만들고 출력하는 메서드
*
* @param r 선택할 요소의 개수
* @param current 현재 선택하는 요소의 index로 최대는 r-1
* @param temp 선택된 요소들이 저장될 배열
* @param visited 요소의 선택 상태를 저장할 정수
*/
private static void makePermutation(int r, int current, char[] temp, int visited) {
if (r == current) {
System.out.println(Arrays.toString(temp));
} else {
for (int i = 0; i < src.length; i++) {
if ((visited & 1 << i) == 0) {
temp[current] = src[i];
makePermutation(r, current + 1, temp, visited | (1 << i));
// 되돌릴 필요는?
}
}
}
}
메서드 선언부에서 달라진 점은 visited에 int []을 사용하지 않고 int를 사용하고 있다는 점이다.
이에 따라 해당 요소의 사용 여부를 확인하기 위해 << 와 &를 사용하고 있다. 방문 처리를 위해서는 <<와 | 연산을 사용한다.
한 가지 주의할 점은 배열을 썼을 때 처럼 다른 호출을 위해 visited를 되돌릴 필요가 없다는 점이다.
배열을 썼을때는 배열이 객체이고 heap에 하나의 배열을 생성한 후 여기 저기서 참조한다. 따라서 되돌려놔야 할 필요가 있지만 단순히 int는 기본형으로 단순히 stack에 local 변수로만 존재하기때문에 다른 메서드의 호출과는 무관하다. 따라서 다시 되돌려 놔야할 필요는 없어진다.
위 메서드들의 실행 결과는 다음과 같다.
[A, B, C]
[A, B, D]
[A, C, B]
[A, C, D]
[A, D, B]
[A, D, C]
[B, A, C]
[B, A, D]
[B, C, A]
[B, C, D]
[B, D, A]
[B, D, C]
[C, A, B]
[C, A, D]
[C, B, A]
[C, B, D]
[C, D, A]
[C, D, B]
[D, A, B]
[D, A, C]
[D, B, A]
[D, B, C]
[D, C, A]
[D, C, B]