순열 : 서로 다른 n개의 원소에서 r개를
순서에 상관있게중복없이 뽑는 것을 순열이라 한다.
C++로 순열을 먼저 만들어보고 그 다음 자바스크립트로 순열을 구현해보기로 했다.
1. C++로 순열 만들기
next_permutation
#include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
vector<int> v;
for(int i = 1; i <= 3; i++){
v.push_back(i);
}
do {
for(int i = 0; i < v.size(); i++){
cout << v[i] << " ";
}
cout << "\n";
} while(next_permutation(v.begin(), v.end()));
return 0;
} 
c++에서는 알고리즘 헤더의 next_permutation 을 통해 순열을 쉽게 만들 수 있다.
next_permutation의 두번째 인자로 포함되지 않는 마지막 주소를 넣어주면 된다.
위 코드에서 v.end()가 아닌 v.begin() + 2와 같이 작성하게 된다면 마지막 주소를 제외한 앞까지만 해당되므로 결과는 다음과 같이 나타난다.
첫번째 요소와 두번째 요소의 자리만 바뀐 값만 출력되었다.
재귀
depth를 기반으로 swap해주는 과정이 필요하다.
#include <bits/stdc++.h>
using namespace std;
vector<int> v;
void makePermutation(int n, int r, int depth){
if(r == depth){
for(int i = 0; i < v.size(); i++){
cout << v[i];
}
cout << "\n";
return;
}
for(int i = depth; i < n; i++){
swap(v[i], v[depth]);
makePermutation(n, r, depth + 1);
swap(v[i], v[depth]); // swap했던 것을 다시 복구시킴
}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
for(int i = 1; i <= 3; i++){
v.push_back(i);
}
makePermutation(3, 3, 0);
return 0;
} 
재귀 함수를 사용할 때는 무한 루프에 빠지지 않도록 반드시 언제 끝나는지 를 작성해줘야 한다.
여기서는 r이 depth와 같을 때 재귀가 종료된다.
2. 자바스크립트로 순열 만들기
재귀
c++로 한번 해봤으니 JS로 순열을 만들어보자.
const arr = [1, 2, 3];
const makePermutation = (n, r, depth) => {
if (r === depth) {
let ret = "";
for (let i = 0; i < arr.length; i++) {
ret += arr[i];
}
console.log(ret);
return;
}
for (let i = depth; i < n; i++) {
[arr[i], arr[depth]] = [arr[depth], arr[i]];
makePermutation(n, r, depth + 1);
[arr[i], arr[depth]] = [arr[depth], arr[i]];
}
};
makePermutation(3, 3, 0);
자바스크립트는 순열을 만들어주는 메서드가 없으므로 재귀를 통해 구현했다.
재귀는 헷갈린다. 😣
재귀는 쓸 때마다 내부 로직이 어떻게 돌아가는 건지 내 머릿속이 돌아가는 기분..
사실 평소에 생각없이 썼는데 이러면 쓸 때마다 또 어떻게 돌아가는거지.. 이러고 있을 것 같아서
아예 재귀를 탈탈 털기로 꼼꼼히 살펴보기로 했다.
먼저 c++ 코드로 makePermutation 함수를 살펴보자.
vector
v에는 [1, 2, 3] 이 담겨있다고 가정한다.
void makePermutation(int n, int r, int depth){
if(r == depth){
for(int i = 0; i < v.size(); i++){
cout << v[i];
}
cout << "\n";
return;
}
for(int i = depth; i < n; i++){
swap(v[i], v[depth]);
makePermutation(n, r, depth + 1);
swap(v[i], v[depth]); // swap했던 것을 다시 복구시킴
}
}처음 시작을 n = 3, r = 3, depth = 0으로 시작한다고 봤을 때 (순서 다르고 중복없게 3개 중 3개 뽑기)
if(r == depth){
for(int i = 0; i < v.size(); i++){
cout << v[i];
}
cout << "\n";
return;
}먼저, 재귀는 무한 루프로 빠지면 안되므로언제 종료되는지! 조건을 작성하는 것이 가장 중요하다.
r이 depth와 동일할 때 현재 백터의 원소들을 출력하고 리턴시켜버려서 재귀를 빠져나가도록 해주었다.
손 코딩하면서 확인하다가 아니 왜 결과랑 다르지?? 싶어서 3시간 동안 헛짓거리(?) 하다가
결국 에디터에서 디버깅해보기로 했다. 진작 디버깅할걸 그랬나.........ㅋㅋㅋ 휴
v[i]는 : 0 depth 는 : 0
v[i]는 : 1 depth 는 : 1
v[i]는 : 2 depth 는 : 2
123
v[i]는 : 2 depth 는 : 1
v[i]는 : 2 depth 는 : 2
132
v[i]는 : 1 depth 는 : 0
v[i]는 : 1 depth 는 : 1
v[i]는 : 2 depth 는 : 2
213
v[i]는 : 2 depth 는 : 1
v[i]는 : 2 depth 는 : 2
231
v[i]는 : 2 depth 는 : 0
v[i]는 : 1 depth 는 : 1
v[i]는 : 2 depth 는 : 2
321
v[i]는 : 2 depth 는 : 1
v[i]는 : 2 depth 는 : 2
312손 코딩 할 때는 123-> 132 -> 213 ... 이렇게 안나오고 123 -> 213 -> 321 이렇게 나와서 왜 132가 안 나오고 213이 나오지 ..하고 세번은 다시 그려봤는데 무한의 인피니트인가 싶어서
결국 디버깅으로 돌려봤다. 😥😥
역시 재귀를 잘못 이해하고 있었던 것 같기도.......... ㅋㅋㅋ ㅠ
드디어 어디가 잘못됐는지 찾았다. 이거만 쳐다본지 약 4시간이 다 되간다.
(나는 바보야 나는 바보야 나는 바보야 나는 바보야)
악필인 건 무시하고..
파란색 화살표로 표시한 부분을 간과하고 있었음을 발견했다.
123이 출력된 시점에서 다시 for문을 타고 가서 i값을 증가시킨 상태에서
makePermutation이 호출되면서 132를 만들고 출력하는 것까지 마쳤어야 했는데!
중간 과정을 계속 생략해버리고 213부터 만들어버렸던 것이 문제였다는 것을 알아냈다.
아~ 재귀는 역시 너무 헷갈린다 또르르ㅡ.. 디버깅이 최고다 정말...
코드가 알아서 돌려준다고 머리로 이해 할 생각을 안했던 것 같다. 이번에 제대로 잡고 가야지.
