[알고리즘] 재귀 함수를 이용한 순열, 조합

순열? 

모든 경우의 수를 계산하는 알고리즘이다. ( 순서 고려 O )

[ 1, 3, 5 ] 가 주어졌다면 

1 3 5 

1 5 3

3 1 5

3 5 1

5 1 3

5 3 1

처럼 모든 경우의 수를 구하는 방법이다. 

function permutations(arr, n) {
  if (n === 1) return arr.map((v) => [v]);
  let result = [];

  arr.forEach((fixed, idx, arr) => {
    const rest = arr.filter((_, index) => index !== idx);
    const perms = permutations(rest, n - 1);
    const combine = perms.map((v) => [fixed, ...v]);
    result.push(...combine);
  });

  return result;
}

만약 arr 로 [ 1, 3, 5 ]가 주어지고 n이 3이라면 

 

if (n === 1) return arr.map((v) => [v]);

통해서 

[ 5 ], [ 3 ], [ 1 ] 이 return 된다. 

 

 const combine = perms.map((v) => [fixed, ...v]);

그것을 기존 배열에서 지운 [ 5 ]인 경우 [ 3 ]과 합쳐져서 [ 3, 5 ]가 되고 

이게 다시 [ 1 ]과 합쳐져서 [ 1, 3, 5 ]가 result 배열에 들어간다. 

 

이런식으로 반복해서 모든 경우의 수를 만들어낸다. 

 

조합 

주어진 배열에서 몇가지 경우의 수가 나오는지 계산하는 알고리즘이다. ( 순서 고려 X )

[ 1, 3, 4, 5 ]가 주어진다면 

1 3 4

1 3 5

1 4 5

3 4 5

의 경우의 수 를 구하는 공식이다. 

 

순열은 순서가 다르면 다른 경우의 수이지만 조합은 순서가 달라도 같은 경우의 수가 된다. 

function combinations(arr, n) {
  if (n === 1) return arr.map((v) => [v]);
  const result = [];

  arr.forEach((fixed, idx, arr) => {
    const rest = arr.slice(idx + 1);
    const combis = combinations(rest, n - 1);
    const combine = combis.map((v) => [fixed, ...v]);

    result.push(...combine);
  });

  return result;
}