[Algorithm] 조합(Combination)과 순열(Permutation) 알고리즘 Javascript

 

조합(Combination) 알고리즘

 

조합은 수를 정렬하는 방법 중 순서를 신경쓰지 않는 방식이다. 임의의 N개의 수로 구성된 집합을 의한다. 순서에 상관없이 m개의 원소를 선택하게 된다. 즉 N개의 원소로 구성된 배열에서 m개의 원소로 구성된 부분 집합을 찾는 과정이다.

 

[1,2,3]의 집합에서 2개의 원소를 출력하라는 문제가 주어질 때 아래 3개의 경우가 참값이 된다.

[1,2]
[1,3]
[2,3]

 

조합의 공식

 

 

 

순열(Permutation) 알고리즘

 

순열은 순서를 고려하여 n개의 집합에서 r개의 원소를 추출하는 작업을 의미한다. 3개의 원소를 가진 배열에서 2개의 원소를 추출한다고 하면 총 6개의 결과값이 도출된다.

[1,2]
[1,3]
[2,1]
[2,3]
[3,1]
[3,2]

 

순열 공식

 

 

 

소스 코드 구현 : 

조합과 순열 문제는 백준 알고리즘에서 찾아볼 수 있다.

순열과 조합의 공식을 사용해서 팩토리얼 재귀 함수를 이용했다. 

/*
  Date : 2022년 5월 14일
  문제 : 백준 2407 조합 알고리즘
  알고리즘 : 재귀 알고리즘
  작성자 : About-Tech
*/

const readline = require('readline');

const r = readline.createInterface({
    input:process.stdin,
    output:process.stdout,
})
// n과 m이 주어진다. (5 ≤ n ≤ 100, 5 ≤ m ≤ 100, m ≤ n)

r.on('line', (item)=>{
        const input = item.split(' ');

        const n = Number(input[0]);
        const m = Number(input[1]);

        const factorial =(n) =>{
            if(n === 0) return 1;
            else
                return n*factorial(n-1);
        }

        const permutation = (n, r) =>{
            const m = n-r;
            return (factorial(n)/factorial(m));
        } 

        const combination = (n, r) => {
            
            return (permutation(n, r)/factorial(r));
        }

        console.log(`Permutation : ${permutation(n, m)}`)
        console.log(`Combination : ${combination(n, m)}`)
        
    r.close();
})

r.on('close', ()=>{
    process.exit();
})

 

결과값 

➜  BaekJoon node 2407_Permutation.js
> 100 5
Permutation : 9034502400
Combination : 75287520