순열 (nPr )
서로 다른 n개에서 r개를 중복 없이 뽑아 순서를 반영하여 그 개수를 구하는 가짓수
for문 재귀 2가지 방법을 통해서 순열을 구현할 수 있다.
for 문
뽑은 알파벳이 a,b,c 일 때 3중 for문을 돌려 완전 탐색을 시켜 순서가 바뀐 배열을 출력한다.
서로의 원소가 겹치는 부분을 제외해서 카운트 해주고 출력을 통해 순열이 잘 이루어졌는지 확인
할 수 있다.
for 문은 직관적이지면 원소의 개수가 늘어나면 개수만큼 for문을 작성해야 한다. 그래서 이해
하기는 어렵지만 재귀를 사용하는 것이 편리하다.
let arr = ['a', 'b', 'c'];
let cnt = 0;
for(let i = 0; i < arr.length; i++) {
for(let j = 0; j < arr.length; j++) {
for(let k = 0; k < arr.length; k++) {
if (i == j) continue;
if (j == k) continue;
if (i == k) continue;
console.log(arr[i], arr[j], arr[k]);
cnt++;
}
}
}
console.log(cnt);
재귀 (긴글 주의 이해되면 유익)
이번의 경우 재귀를 통해 작성한 코드이다. 재귀는 좀 이해하기가 어렵다. 필자의 경우 아래 코드만 이해
하는데 3 ~ 4 시간 정도 걸린 것 같다. 그 말인 즉슨 여러분도 이해 할 수가 있다. 아래 코드를 손으로
한줄 한줄 추적해나가면서 느낀건 재귀를 이해하기 위해서는 작은단위가 아닌 큰 단위로 나누어서 이해해야
한다는 것이었다.
우선 for문을 눈여겨 볼 필요가 있다. 아래 for문은 s에 0을 넣으면 i가 0부터 2까지 도는 for문이다. 이
부분을 먼저 짚고 아래 코드를 이해해야 한다. 즉 크게는 i = 0, 1, 2 이렇게 세번 돈다고 보아도 무방하다
는 의미이다.
for (let i = s; i < arr.length; i++) {
[arr[s], arr[i]] = [arr[i], arr[s]];
permutation(arr, s+1, r);
[arr[s], arr[i]] = [arr[i], arr[s]];
}
두번째는 [arr[s], arr[i]] = [arr[i], arr[s]] 이 부분인데, 원본 arr의 내용에 변경을 주면서 자리를
스위치 해주는 부분이다. (i != s)일 때 자리 전환이 이루어 지는 부분이고 (i===s)이면 같으니까 전환이
이루어져도 원본 값이 전과는 같다.
이제 대망의 재귀부분인데 재귀는 자기자신을 호출하는 것으로 이해 할 수 있고 반드시 끝나는 조건을 명시해
주어야한다. 그렇지 않으면 자기자신을 계속 호출하기 때문에 컴터가 에러를 뱉는다. 그때의 조건을 기저조건
이라고 하고 아래 코드의 기저조건은 (s==r)일 때이다. 그 아래 코드를 이해하기 앞서 우선 (s==r)인 부분을
먼저 이해해보자.
여기서 s는 index의 시작 위치이다. for문에서 permutation(arr, s+1, r);로 인해 s의 값은 1이 증가
하는데 이 값이 r과 같아지면 재귀로 호출한 함수가 종료가 된다. 여기서 r은 마지막 인덱스이다.
위의 내용을 봤으니 이제 코드를 찬찬히 살펴보자 s=0 일때 i=0이다. 인덱스가 같으므로 자리 전환이 발생하지
않는다.
재귀로 들어가면 s값이 증가하니 s=1 i=1인 값으로 자기자신을 호출하게 된다.
permutation(arr, s+1, r);
함수의 첫번째 호출을 포함하여 총 2번의 호출이 있었고, 아직 기저조건에 도달하지 못했다. 이말인 즉슨
2번의 depth가 생겼다는 의미이다. s가 i의 초기 값을 결정하므로 s값이 1증가해 1이되면 i=1이 된다.
s=1 i=1 일 때 index의 값이 같아 원본 배열의 변화는 일어나지 않는다. 즉 ['a', 'b', 'c']이다.
그 상태에서 다시 자기 자신을 호출 함으로서 3번의 depth가 생기면서 s=2 i=2이 된다. 드디어 기저조건에 도
달 하게 되었다.
기저 조건에 도달했으므로 count를 1 증가시키고 abc가 출력되면서 첫번째로 함수의 막을 내렸다. 즉 permutation
(['a','b','c'], 2, 2)로 호출한 함수가 처음으로 종료되는 시점이라고 할 수 있다.
해당 함수가 종료되고 나면 [arr[s], arr[i]] = [arr[i], arr[s]]; 을 실행 하는 것을 끝으로 배열을 그 전
상태로 돌려 놓는다. 인덱스의 변화가 없으므로 변화는 없지만 인덱스가 달라 변화가 발생한 케이스에 대해선 원래
대로 돌려 놓는 역할을 한다.
컴퓨터는 그 전타임에 호출했던 s=1 i=1 부분으로 돌아간다. 여기서 쌓이다(stack)라는 개념이 생기는데 함수는
호출할 때 마다 블록처럼 위에 쌓이고 기저조건을 만나면 블록이 다시 없어지는 식으로 진행된다. 여기서는 그 전 블
록이 s=1 i=1인 permutation(['a','b','c'], 1, 1)인 부분이고 for (let i = s; i < arr.length; i++) 부
분으로 인해 i는 아직 arr 길이가 3보다 작으므로 s=1 i=2인 상태에서 다시 진행된다. 이때의 depth는 2이다.
여기서 depth라는 개념을 확인할 수 있는데 함수가 쌓인 층의 개수로 이해하면 된다. 지금 2개의 함수가 쌓였고 맨
위층에 있는 함수가 s=1 i=2 값으로 아래 식에 돌입하려고 하는 것이다.
[arr[s], arr[i]] = [arr[i], arr[s]];
index가 서로 다르므로 (s!=i) 배열에 변화가 생기고 1과 2의 위치를 바꾸는 것이기 때문에 ['a', 'c', 'b']
로 arr의 변화가 생긴다. 그리고 다시 자기 자신을 호출하게 된다. depth가 3이다.
permutation(['a', 'c', 'b'], 2, 2)로 진입하게 되고 기저조건을 충족하므로 카운트 개수를 1증가시키고
acb 배열을 출력시킨다. 그리고 해당 블록은 해제 되므로 다시 depth는 2가 된다.
재귀가 끝낸 이후 [arr[s], arr[i]] = [arr[i], arr[s]]; 식을 실행하게 되면 arr는 ['a', 'c', 'b']
에서 ['a','b','c']로 돌아가게 되고 s=0 일때 i=1인 값으로 앞에서 크게 3번 돈다고 했을 때 i가 1일 때인
2번째 도는 시점에 돌입하게 되는 것이다.
첫번째 사이클을 도는 과정이 위와 같고 i=1일때 i=2일 때의 상황도 위와 동일한 절차를 밟는다고 생각하면 된다.
아래는 재귀코드 전문이고 작은 경우의 수부터 손으로 하나씩 써보면서 그 과정을 추적하다 보면 이해가 될 것이라고
생각한다.
다만 지금까지의 글은 재귀 자체를 이해하는 코드이었기에 어떻게 하면 원소개 3개인 배열의 순열을 구할 때 다음과
같이 코드를 작성할 수 있을까에 대한 부분은 다른 부분이라서 이 부분은 별도로 정리해야 할 것 같다.
let input = ['a', 'b', 'c'];
let count = 0;
function permutation(arr, s, r) {
if (s == r) {
count++;
console.log(arr.join(""));
return;
}
for (let i = s; i < arr.length; i++) {
[arr[s], arr[i]] = [arr[i], arr[s]];
permutation(arr, s+1, r);
[arr[s], arr[i]] = [arr[i], arr[s]];
}
}
permutation(input, 0, 2);
console.log(count);
