C++로 문제를 풀 때는 순열, 조합 라이브러리가 존재해서 그냥 사용했었는데 자바스크립트에는 따로 존재 하지 않아 직접 구현해야 했다. 그래서 자바스크립트로 구현하는 순열, 조합을 정리해보려고 한다!

조합

const alphabet = ['a', 'b', 'c', 'd'];
const L = 2;
const combi = [];
const combinations = (str, k) => {
    if(str.length === L ){
        combi.push(str);
        return;
    }
    else{
        for(let i = k; i<C; i++){
            combinations(str + alphabet[i], i+1);
        }
    }
}
console.log(combi('',0);
// [ 'ab', 'ac', 'ad', 'bc', 'bd', 'cd' ]

위의 예시는 4C2를 구하는 코드인데 함수안에 for문이 처음에는 이해가 어려울 수 있다.
간단하게 생각하면 배열에서 원소 하나씩을 뽑는데 하나를 뽑고 나면 그 이후의 원소들에서 하나 씩 계속 뽑아서 원하는 길이가 될 때 까지 뽑는 것이다.

위의 예시에서는

제일 처음에 a가 뽑히고 a를 제외한 b,c,d중 b를 다시 뽑게 되는데 이 때 문자열의 길이가 2가 되었으므로 ab가 만들어지고 종료되고 그 다음 c,d 순으로 뽑고 ac, ad가 배열에 들어가게 된다.
a에 대한 처리가 끝나면 다음에는 b가 뽑히고 b를 제외한 c,d에서 c,d가 뽑혀 bc, bd가 완성되고 배열에 들어간다. 이런 과정으로 조합을 구현할 수 있다.

순열

const alphabet = ['a', 'b', 'c', 'd'];
const permu = [];
const C = 4;
const permutation = (arr, str) => {

    if(str.length === C){
        permu.push(str);
        return;
    }
    
    else{
        for(let i = 0; i<arr.length;i++){
            const temp = [...arr.slice(0,i), ...arr.slice(i+1)]
            permutation(temp, str+arr[i]);
        }
    }

}
permutation(alphabet, '');
console.log(permu);
//[
  'abcd', 'abdc', 'acbd',
  'acdb', 'adbc', 'adcb',
  'bacd', 'badc', 'bcad',
  'bcda', 'bdac', 'bdca',
  'cabd', 'cadb', 'cbad',
  'cbda', 'cdab', 'cdba',
  'dabc', 'dacb', 'dbac',
  'dbca', 'dcab', 'dcba'
]

순열도 조합처럼 재귀를 이용해 구현할 수 있다.

순열은 const temp = [...arr.slice(0,i), ...arr.slice(i+1)] 이 부분만 이해하면 크게 어렵지 않다!

조합에서 했던 것 처럼 특정길이가 될 때 까지 문자를 뽑게 되는데 조합에서는 하나의 배열을 가지고 처리를 했지만 여기서는 또 다른 배열들을 만들어줘야 한다. 이 때 위의 코드가 사용이 되는데
...arr.slice(0,i)는 배열에서 원소하나를 뽑았을 때 해당 원소보다 앞에 있는 값들을 의미하고
...arr.slice(i+1)은 배열에서 원소하나를 뽑았을 때 해당 원소보다 뒤에 있는 값들을 의미한다.

하나를 뽑고 그 원소를 제외한 배열들을 다음 호출에 넘겨주는 것!

위의 예시에서 'bacd'가 어떻게 만들어졌는지 생각해봅시다.

a를 제일 앞에 놓는 재귀 호출이 끝나고 b가 시작이 될텐데

b를 뽑고나면 a,c,d 배열을 만들어서 다음 호출에 넘겨준다.

여기서 a를 뽑고 c,d 배열을 만들어서 다음 호출에 넘겨준다.

여기서 c를 뽑고 d 배열을 만들어서 다음 호출에 넘겨준다.

d가 뽑히고 'bacd'가 완성되어 배열에 들어간다.

그 다음은 'badc'가 완성이 되는데

a를 뽑고 c를 뽑았었는데 그 다음은 d이다.

여기서 d를 뽑게되고 c배열을 만들고 다음 호출에 넘겨준다.

그리고 c를 뽑아서 'badc'가 된다.

나머지 과정도 위와 같이 생각하면 된다.

정리

자바스크립트에는 순열, 조합 메서드가 따로 존재하지 않기 때문에 글로 정리해보았다.

순열에서는 하나를 뽑고 그 하나를 포함하지 않은 배열을 만들어서 넘겨주는 것이 중요하다.

조합에서는 하나를 뽑고 그 하나를 포함하지 않게 다음 원소를 선택하게 하면 된다. 조합에서는 순서가 중요하지 않기 때문에 배열을 새로 만들 필요는 없다.