[알고리즘] 순열과 재귀함수

sehannnnnnn.log 님의 [알고리즘 JS] - 순열과 조합 구현 (자바스크립트)
글 기반으로 제가 이해가 안되는 부분을 첨가하여 작성하였습니다.

순열

서로 다른 n개 중 r개를 골라 순서를 정해 나열하는 가짓수이다. 영어로 Permutation의 첫 글자 P를 따서 nPr로 표시한다.

예를 들어 서로 다른 수 3개([1, 2, 3] 이라고 가정) 중 3개를 골라 순서를 정해 나열한다면 6가짓수가 나오고 각 경우는 아래와 같다.

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

순열 재귀함수로 해결하는 의사코드

0. 기초 환경 셋팅
   순열대상: [1, 2, 3]
====
1. 재귀 함수 호출 인자 
	1. selection(선별 배열) : [] 빈 배열로 초기화 한다.
    2. rests(나머지 배열) : [1, 2, 3] 순열대상 배열로 초기화 한다.
    3. output(각 가짓수 별 배열) : [] 빈 배열로 초기화 한다.
====
2. if rests(나머지 배열).size = 0 탈출조건: 나머지 배열의 길이가 0이면 함수 종료 
   true: 
   		output.push(selection: 선별 배열) 선별 배열을 output 배열에 추가
        return
====
3. for rest of rests 나머지 배열을 순회한다.
	1. _selection 선별 배열에 순회된 값을 추가한다.
    2. _rests 선별 배열에 넣은 값을 제외한 나머지 값으로 새로운 배열을 생성한다.
    3. self(_selection, _rests, output) 재귀호출을 한다.

의사코드 바탕으로 Javascript 소스로 구현하면 아래와 같다.

const array = [1, 2, 3];
const output = [];

permutation([], array, output);

const permutation = (selection, rests, output) => {
  // 탈출조건
  if(!rests.length) {
    output.push(selection);
    return;
  }
        
  rests.forEach((item, index) => {
    const _selection = [item, ...selection];    
    const _rests = [...rests.slice(0, index), ...rests.slice(index + 1)];
    permutation(_selection, _rests, output);
  });
}

재귀함수 프로세스

예제 배열) [1, 2, 3]: array
1. []: selection, [1, 2, 3]: rests, []: output
2. [1], [2, 3], []
	2-1. [1, 2], [3], []
    2-1-1. [1, 2, 3], [], [] V 탈출조건
    2-2. [1, 3], [2], []
    2-2-1. [1, 3, 2], [], [] V 탈출조건
3. [2], [1, 3], []
	3-1. [2, 1], [3], []
    3-1-1. [2, 1, 3], [], [] V 탈출조건
    3-2. [2, 3], [1], []
    3-2-1. [2, 3, 1], [], [] V 탈출조건
4. [3], [1, 2], []
	4-1. [3, 1], [2], []
    4-1-1. [3, 1, 2], [], [] V 탈출조건
    4-2. [3, 2], [1], []
    4-2-1. [3, 2, 1], [] [] V 탈출조건
=======================================
output: [1,2,3] [1,3,2] [2,1,3] [2,3,1] 
        [3,1,2] [3,2,1]

Reference

[알고리즘 JS] - 순열과 조합 구현 (자바스크립트)
두산 백과 - 순열