알고리즘 공부를 하면서 자주 등장하는 개념인 순열과 조합에 대해서 정리해보기.

순열(Permutation)

개념

순열이란, 서로 다른 n개의 원소에서 r개를 중복없이 순서에 상관 있게 선택 또는 나열하는 것을 말한다. 즉 예를 들어 123과 213을 다르게 취급한다는 특징이 있다.

구현

const 순열구하기 = (array, r) => {
  const visit = Array.from({length: array.length}, () => 0);
  const temp = Array.from({length:r}, () => 0);
  const result = [];
  
  const DFS = (level) => {
  	if(r === level){ // 레벨과 뽑을 수가 같아지면 결과값에 푸쉬(123, 132 등)
    	result.push(temp.slice());
    } else{
    	for(let i = 0; i<array.length; i++){
        	if(visit[i] === 0){
            	visit[i] = 1; // 체크를 하고
				temp[level] = array[i]; // 값을 넣어주고
              	DFS(level+1); // 다음 레벨로 넘기고
   	            visit[i] = 0; // 끝났으니 체크를 초기화 해주기
            }
        }
    }
    
  }
  DFS(0)
  return result
}

조합(Combination)

개념

조합은 서로 다른 n개의 원소에서 r개를 선택하는 것은 순열과 비슷하지만 순서가 상관 없다는 점이 차이가 있다. 즉, 123과 213을 동일하게 취급한다.

구현

const 조합구하기 = (array, r) => {
  const temp = Array.from({length:r}, () => 0);
  const result = [];
  
  const DFS = (level, start) => {
  	if(r === level){ // 레벨과 뽑을 수가 같아지면 결과값에 푸쉬(12,13 등)
    	result.push(temp.slice());
    } else{
    	for(let i = start; i <= array.length; i++){
          temp[level] = i; // 값을 넣어주고
          DFS(level+1, i+1); // 다음 레벨로 넘기고  
        }
    }
    
  }
  DFS(0,1)
  return result
}