[알고리즘] 순열과 조합 - javascript

📌조합 (Combination)

n개 중에서 m개를 선택하는 경우의 수 (nCr = n개 중 r개의 combination)

조합은 순서 상관 없음 ⇒ [1,2] & [2,1]은 같은 것으로 취급
 
ex) Input: [1, 2, 3, 4]
Output: [ [1, 2, 3], [1, 2, 4], [1, 3, 4], [2, 3, 4] ]
 

코드 구현 원리

조합을 구현하는 원리는 다음과 같다.

 
let arr = [1,2,3,4];

// arr에서 3개를 선택하는 경우의 수 구하기
 

0. 시작
1. 1을 선택(고정) -> 나머지 [2, 3, 4] 중에서 2개씩 조합을 구함 => [1, 2, 3] [1, 2, 4] [1, 3, 4]
2. 2를 선택(고정) -> 나머지 [3, 4] 중에서 2개씩 조합을 구함 => [2, 3, 4]
3. 3을 선택(고정) -> 나머지 [4] 중에서 2개씩 조합을 구함 => []
4. 4을 선택(고정) -> 나머지 [] 중에서 2개씩 조합을 구함 => []
5. 종료

 
맨 앞의 하나를 고정하고, 나머지 중에서 조합을 구해서 고정수와 더해준다.
이 과정은 재귀 함수가 필요하다.
이를 바탕으로 코드를 구현해보자.
 

구현

function permutation(arr, selectNum) {

    const result = []; // 1
    if (selectNum === 1) return arr.map(v => [v]); // 1. 재귀 종료 조건: 1개 고르면 바로 요소담은 배열 반환

    arr.forEach((v, idx, arr) => {
        const fixed = v; // 숫자 하나 고정
        const restArr = arr.slice(index + 1); // 2. 해당하는 fixed를 제외한 나머지 뒤
        const restPermutations = permutation(restArr, selectNum - 1); // 3. 나머지에 대해서 조합을 구한다.
        const combineFixed = restPermutations.map(v => [fixed, ...v]); // 4. 조합에 떼 놓은(fixed) 값 붙이기
        result.push(...combineFixed); // 5. result에 값 추가
    });
    return result;
   // 재귀가 진행중이면 해당 값이 restPermutations의 반환값이 되어 combineFixed를 통해 fixed와 결합함
}

console.log(permutation([1,1,7]));
// [[1, 1], [1, 7], [1, 1], [1, 7], [7, 1], [7, 1]]

 

1. 원소 1개의 조합을 구한다고 하면 바로 요소 하나씩 배열로 만들어서 return

   ex) arr = [1,2,3,4] / selectNumber = 1 ⇒ return [[1], [2], [3], [4]]
    

2. 맨 첫번째 값부터 선택됨 (선택값 = fixed) → rest = fixed 뒤부터 맨끝까지의 배열

   ex) arr = [1,2,3,4] / fixed = 1 (맨 처음 순회라면) / rest = [2,3,4]
    

3. 재귀함수 호출

   코드가 어떻게 실행될지 모르겠다면, 재귀가 종료조건을 만났을 때 반환값이 무엇일지 계산하고 이를 바탕으로 계산하면 된다.

   위 코드는 맨 마지막에 selectNumber = 1 이면 반환값이 [[3], [4]]가 된다.
    

4. fixed와 조합 합치기

   함수에서 반환된 경우의 수와 고정해놨던 fixed를 합쳐준다.
   위에서 예로 든 반환값 [[3], [4]]가 [[2,3], [2,4]]가 되는 것이다.
    

5. 차곡차곡 result 배열에 반환값이 쌓임

   이 값은 result에 쌓여 반환되게 되고, 재귀가 진행중이면 해당 값이 restPermutations의 반환값이 되어 combineFixed를 통해 fixed와 결합한다.
   (재귀함수가 호출되면서 result가 재선언되지만, 그건 재귀함수 안에서고 부모 함수에는 영향을 미치지 않는다)
    

📌순열 (Permutation)

순열은 조합에서 순서까지 신경 쓴 것이다.
고로 nCr x 3! = nPr ( n! = n x (n-1) x ... x 1)
 

코드 원리

1(fixed) => permutation([2, 3, 4]) => 2(fixed) => permutation([3, 4]) => ...
2(fixed) => permutation([1, 3, 4])
3(fixed) => permutation([1, 2, 4])
4(fixed) => permutation([1, 2, 3])

 
위 조합과 비슷하지만, 고정숫자 이외의 요소들 중 하나를 또 고정하고 같은 과정을 반복한다.
그렇기 때문에 똑같이 재귀함수의 인자로 전달하는 배열을 조합과 달리 해야한다.
 

구현

function permutation(arr, selectNum) {

    const result = [];
    if (selectNum === 1) return arr.map(v => [v]); // 재귀 종료 조건: 1개 고르면 바로 요소담은 배열 반환

    arr.forEach((v, idx, arr) => {
        const fixed = v; // 숫자 하나 고정
        const restArr = arr.filter((e, index) => index !== idx); // ★ fixed를 제외한 나머지 배열 생성
        const restPermutations = permutation(restArr, selectNum - 1);
        const combineFixed = restPermutations.map(v => [fixed, ...v]); // 구한 순열에 fixed 붙이기
        result.push(...combineFixed); // result에 순열 추가
    });
    return result;
}

 
조합 코드에서 ★ 부분만 다르다.
조합은 순서가 달라도 같다고 취급하는 반면, 순열은 순서가 다르면 다르다고 보기 때문에 고정 요소를 제외한 모든 요소를 넘겨준다.
 

---

참고

https://jun-choi-4928.medium.com

https://pul8219.github.io

https://velog.io/@proshy