조합과 순열

1. 조합

조합의 경우에는 순서가 중요하지 않기 때문에 중복되는 것을 빼고 뽑는다.

ex) 1,2,3,4 숫자를 이용한 조합

=> [1,2], [1,3], [1,4], [2,3], [2,4], [3,4]

2. 순열

순열의 경우 순서가 중요하기 때문에 중복되는 값([a,b], [b,a]과 같은 값들)이 있어도 다 뽑는다.

순서를 고려한다는 것은 순서가 바뀌면 다른 것으로 취급함을 의미한다. 

ex) 1,2,3,4 숫자를 이용한 순열

=> [1,2], [1,3], [1,4], [2,1], [2,3], [2,4], [3,1], [3,2], [3,4], [4,1], [4,2], [4,3]

3. 요약

서로 다른 3개의 문자 A,B,C에서 2개를 택하는 순열, 중복순열, 조합, 중복조합

4. 구현 

아래 코드로 순열, 중복순열, 조합, 중복조합을 만들 수 있다.

function getCombinations(arr, combineNum) {
            let result = []; // 리턴 배열

            if (combineNum == 1) {
                return arr.map((dr) => [dr]);
            }
            // 조합할 수가 1이면 모든 배열의 원소 리턴

            arr.forEach((fixed, idx, origin) => {
                let rest = [];
                
                // 아래 4가지 방법으로 각 조합,중복조합,순열,중복순열을 만들 수 있다.
                
                rest = origin.slice(idx + 1); 
                // => 해당 fixed값 다음부터 모든 값 이므로 겹치는 값이 없음 ( 조합 )
                
                rest = origin.slice(idx); 
                // ( 중복조합 )
                
                rest = [...origin.slice(0, idx), ...origin.slice(idx + 1)]; 
                // => fixed값을 제외한 모든 값 겹치는 값이 있음 ( 순열 )
                
                rest = origin 
                // ( 중복순열 )

                let combination = getCombinations(rest, combineNum - 1); // 나머지에 대한 조합 값
                let attached = combination.map((br) => [fixed, ...br]); // 나온 결과 값에 대해 fixed값 붙어기
                result.push(...attached); // 리턴 배열에 넣어주기
            });

            return result
        }

 

★ 순열과 조합은 알고리즘 풀이에 자주 사용하므로 개념 및 코드에 대해 확실하게 이해하자!

 

 

*참고

https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=alwaysneoi&logNo=100155625557 

[순열, 중복순열, 조합, 중복조합] 순서와 중복의 차이