[Algorithm] 기초(2) 순열과 조합

순열(Permutation) / 조합(Combination)

• 순열은 서로 다른 n개 중에 r개를 선택해 순서를 고려해 나열한 경우의 수를 말한다.

• 중복 순열은 서로 다른 n개 중에 r개를 중복을 허용해 뽑아서 정렬하는 경우의 수를 말한다.

// 순열
const getPermutation = (arr, num) => {
  let result = [];
  if (num === 1) {
    return arr.map((el) => [el]);
  }
  arr.forEach((fixed, idx, origin) => {
    let rest = origin.filter((_, index) => index !== idx);
    let combinations = getPermutation(rest, num - 1);
    let attached = combinations.map((el) => [fixed, ...el]);
    result.push(...attached);
  });
  return result;
};

let output1 = getPermutation([1,2,3], 3)
console.log(output1)
/* 
[
  [ 1, 2, 3 ],
  [ 1, 3, 2 ],
  [ 2, 1, 3 ],
  [ 2, 3, 1 ],
  [ 3, 1, 2 ],
  [ 3, 2, 1 ]
]
*/

// 중복 순열
const getOverlapPermutation = (arr, num) => {
  let result = [];
  if (num === 1) {
    return arr.map((el) => [el]);
  }
  arr.forEach((fixed, origin) => {
    let rest = origin;
    let combinations = getOverlapPermutation(rest, num - 1);
    let attached = combinations.map((el) => [fixed, ...el]);
    result.push(...attached);
  });
  return result;
};

let output2 = getOverlapPermutation([1,2,3], 3)
console.log(output2)
/*
[
  [ 1, 1 ], [ 1, 2 ],
  [ 1, 3 ], [ 2, 1 ],
  [ 2, 2 ], [ 2, 3 ],
  [ 3, 1 ], [ 3, 2 ],
  [ 3, 3 ]
]
*/

• 조합은 서로 다른 n개 중에 r개를 선택하는 경우의 수를 말한다. 순열과 달리 순서를 고려하진 않는다.

• 중복 조합은 서로 다른 n개 중에 r개를 중복을 허용해 뽑는 경우의 수를 말한다.

// 조합
const getCombination = (arr, num) => {
  let result = [];
  if (num === 1) {
    return arr.map((el) => [el]);
  }
  arr.forEach((fixed, idx, origin) => {
    let rest = origin.slice(idx + 1);
    let combinations = getCombination(rest, num - 1);
    let attached = combinations.map((el) => [fixed, ...el]);
    result.push(...attached);
  });
  return result;
};

let getCombination([1,2,3], 2)
console.log(output1)
/*
[ [ 1, 2 ], [ 1, 3 ], [ 2, 3 ] ]
*/

// 중복 조합
const getOverlapCombination = (arr, num) => {
  let result = [];
  if (num === 1) {
    return arr.map((el) => [el]);
  }
  arr.forEach((fixed, idx, origin) => {
    let rest = origin.slice(idx);
    let combinations = getOverlapCombination(rest, num - 1);
    let attached = combinations.map((el) => [fixed, ...el]);
    result.push(...attached);
  });
  return result;
};

let output2 = getOverlapCombination([1,2,3], 3)
console.log(output2)
/*
[
  [ 1, 1, 1 ], [ 1, 1, 2 ],
  [ 1, 1, 3 ], [ 1, 2, 2 ],
  [ 1, 2, 3 ], [ 1, 3, 3 ],
  [ 2, 2, 2 ], [ 2, 2, 3 ],
  [ 2, 3, 3 ], [ 3, 3, 3 ]
]
*/

순열과 조합은 코딩 테스트에서 매우 빈번하게 사용되는 도구니 반드시 숙지하고 넘어가자!!

멱집합

멱집합(powerset)은 주어진 집합의 모든 부분 집합들로 구성된 집합을 말한다. 자바스크립트로 구현해보면 다음과 같다.

const powerSet = function (arr) {
  let flag = new Array(arr.length).fill(false);
  const subSets = [];

  const subSet = function DFS (depth) { // 부분 집합 구하는 재귀 함수, DFS 알고리즘
    if (depth === arr.length) { // 트리의 끝에 다다른 것 ==> 재귀 종료 조건
      const subSet = arr.filter((value, index) => flag[index]); // 해당 flag true => 부분집합 포함
      subSets.push(subSet); // 부분집합들을 담는 배열에 push
      return;
    }
    flag[depth] = true; // 해당 depth의 flag true = 트리의 왼쪽
    subSet(depth + 1); // 트리의 왼쪽에 대해 재귀호출
    
    flag[depth] = false; // 해당 depth의 flag false = 트리의 오른쪽
    subSet(depth + 1); // 트리의 오른쪽에 대해 재귀 호출
  }
  
  subSet(0); // depth 0 부터 시작
  return subSets;
}

let output = powerSet([1,2,3]);
console.log(output); // [[ 1, 2, 3 ], [ 1, 2 ], [ 1, 3 ], [ 1 ], [ 2, 3 ], [ 2 ], [ 3 ], []]

물론 문자열도 가능하다.

const powerSet = function (str) {
  // 1. 문자열을 배열로 만든다.
  // 2. 문자열을 정렬한다.
  // 3. 중복된 문자열은 제거한다.
  const arr = str.split('').sort().reduce((a, c) => {
    if( a[a.length-1] === c ) return a;
    return a.concat(c);
  }, []);

  // 4. 부분집합을 담을 배열을 선언한다.
  const subSets = [];

  // 5. 부분집합은 ''으로 시작해서 중복을 제거한 길이만큼까지의 조합을 구한다.
  const pickOrNot = (idx, subset) => {
    if( idx === arr.length ) {
      subSets.push(subset);
      return;
    }
    // 현재 내가 'a' 이면 idx가 arr.length 해서 return 되기 전에는 아래 재귀는 실행되지 않는다.
    pickOrNot(idx + 1, subset);
    // 위의 재귀가 return 되면서 idx가 줄어들어가면서 아래 재귀가 실행된다. (여기에서 문자열이 집합된다.)
    pickOrNot(idx + 1, subset + arr[idx]);
  };

  pickOrNot(0, '');
  subSets.sort();

  return subSets;
};

let output1 = powerSet('abc');
console.log(output1); // ['', 'a', 'ab', 'abc', 'ac', 'b', 'bc', 'c']

let output2 = powerSet('jjump');
console.log(output2); // ['', 'j', 'jm', 'jmp', 'jmpu', 'jmu', 'jp', 'jpu', 'ju', 'm', 'mp', 'mpu', 'mu', 'p', 'pu', 'u']