data structures - 순열

순열이란?

서로 다른 n개의 원소에서 r(단,0<r≤n일 때)개를 중복없이 순서를 고려하여 선택하거나 나열하거나 하는 것을 순열(permutation)이라고 한다.
순열은 초등학교 때부터 알게 모르게 써왔던 수학 개념 중 하나다
서로 다른 n개 중에 r개를 선택하는 경우의 수 (순서O, 중복X)
예1) 예1) 5명을 3줄로 세우는 방법
예2) 서로 다른 4명 중 반장, 부반장을 뽑는 방법

재귀 함수를 이용한 순열

let getPermutation = (arr,selectnum)=>{
	const result = []; // 결과를 담을 배열
    if (selectnum === 1){ // 순열의 길이가 1이면 각 원소를 배열로 반환
    	arr.map((v)=>[v]);
    }
    arr.forEach((fixed, index, origin)=>{ // 각 원소에 대해 순열 생성
    	const rest = [...origin.slice(0, index), ...origin.slice(index + 1)]; // 고정 원소를 제외한 나머지 원소들
        const permutation = getPermutation(rest, selectnum - 1); // 나머지 원소들에 대해 순열 생성
        const fixed_permutation = permutation.map((v)=>[fixed, ...v]); // 고정 원소와 나머지 원소들의 순열을 결합
        result.push(...fixed_permutation);
    });
    return result;
}

순열은 중복을 허용하며 모든 경의 수를 조합할 수 있다.

예를 들어 1,2,3과 1,3,2를 다른것으로 취급한다.