[JS] 조합과 순열 알고리즘

조합

서로 다른 n개의 물건에서 순서를 생각하지 않고 r개를 선택하는 것이며. nCr로 표기한다.

input, output 예시

input : [1, 2, 3, 4]
4C3
output: [[1,2,3], [1,2,4], [1,3,4], [2,3,4]]

이를 수도 코드로 나타내면

1을 선택하고, 나머지 [2,3,4] 중에서 2개씩 조합을 구한다
-> [1,2,3][1,2,4] [1,3,4]
2를 선택하고, 나머지 [3,4] 중에서 2개씩 조합을 구한다
-> [2,3,4]
3을 선택하고, 나머지 [4] 중에서 2개씩 조합을 구한다
-> []
4를 선택하고, 나머지 [] 중에서 2개씩 조합을 구한다
-> []

이 과정을 코드로 나타내면 다음과 같다.

const getCombination = (arr, selectNum) => {
	const results = [];
	if (selectNum === 1) return arr.map((el) => [el]); //r이 1이라면 [el] 배열 반환

	arr.forEach((fixed, i, origin) => {
		const rest = origin.slice(i + 1); //fixed된 영역 뒤의 나머지 배열
		const combinations = getCombination(rest, selectNum - 1); //나머지 배열로 r - 1 개를 만드는 조합
		const attached = combinations.map((a, i) => [fixed, ...a]); //고정된 값들과 나머지 값들로 만든 조합을 합친다
		results.push(...attached);
	});

	return results;
}

순열

서로 다른 n개의 물건 중에서 r개를 택하여 한 줄로 배열하는 것. nPr로 표기한다.
조합은 순서에 상관 없이 선택한 것이지만, 순열은 순서가 중요하다.

로직은 조합과 거의 비슷하지만, 선택된 값 외의 나머지 요소 배열을 구하는 방법이 달라진다.

const getPermutations = (arr, selectNum) => {
  const results = [];
  if (selectNum === 1) return arr.map((el) => [el]);

  arr.forEach((fixed, i, origin) => {
    //선택된 요소 하나만을 제외한 배열을 rest로 지정해준다
    const rest = [...origin];
    rest.splice(i, 1);
    const permutations = getPermutations(rest, selectNum - 1);
    const attached = permutations.map((a, i) => [fixed, ...a]);
    results.push(...attached);
  });

  return results;
};

참고자료

https://velog.io/@devjade/JavaScript%EB%A1%9C-%EC%88%9C%EC%97%B4%EA%B3%BC-%EC%A1%B0%ED%95%A9-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EA%B5%AC%ED%98%84%ED%95%98%EA%B8%B0