자바스크립트 모든 부분 집합(멱집합) 구하기

📌  멱집합 PowerSet?

 

구할 수 있는 모든 부분 집합의 집합 === 멱집합

"모든 부분집합 모음"이라고 쉽게 생각하자.

 

예를 들어, [1, 2, 3, 4, 5]와 같은 배열의 멱집합을 구한다고 한다면,

말 그대로 "부분" 집합이니까 각 요소들은 "있다"vs"없다" 라는 2가지 상태를 지닐 수 있다.

1이 있어도 부분집합, 없어도 부분집합이다. (믿기지 않겠지만 빈 배열도 부분집합으로 친다 !)

 

그래서 2(가지 상태)^5(요소 개수) 32개의 부분집합을 구할 수 있다.

32개의 부분집합을 모두 담은 집합을 멱집합이라고 할 수 있다.

 

 

📌  Tree로 구현하기

 

 

DFS완전 탐색을 이용해 그려보면, 일정한 패턴을 볼 수 있다.

왼쪽 노드를 선택했을 때 오른쪽 노드는 선택되지 않는다.

"있다"와 "없다" 2가지 상태 중 하나만 선택하는 것처럼 선택했던 노드는 중복 선택하지 않는다.

 

이 Tree는 같은 DEPTH깊이에 위치한 노드의 값이 모두 동일하다.

때문에 한쪽 방향의 노드만 선택하며 완전 탐색을 했을 때 결과값이 나오게 된다.

 

📌  코드로 구현하기

 

[1, 2, 3, 4, 5]의 부분집합을 구해라 ! 라는 문제가 주어졌을때

0개, 1개, 2개, 3개, 4개, 5개 즉 개수를 나눠 생각한다.

어떤 숫자가 쓰였고, 어떤 숫자가 쓰이지 않았는지 (머리속으로는) 알기 때문에 개수로 나눠 파바박 구할 수 있다.

 

그러나 컴퓨터는 해당 숫자의 사용 여부를 알지 못한다.

모든 요소를 훑으면서 검색할 수는 있어도 기억하지는 못한다.

그렇기 때문에 사용했는지, 사용하지 않았는지 상태를 따로 기록해줘야한다.

 

아래 코드를 보면 알 수 있듯, 노드를 지나가면서 왼쪽 노드에만 true 값을 주며 depth를 더해갔다.

depth 값이 배열의 길이와 같아지면, 즉 마지막 노드에 도착했을 때 지나간 흔적을 참고하여 배열을 filtering 해주었다.

ex. 지나간 노드 표식 : [false, true, false]  -->  모든 노드를 훑었고, 그 중 인덱스1값만 왼쪽 노드에 위치했었다는 걸 알 수 있다.

      true가 위치한 인덱스와 같은 인덱스에 있는 배열값을 새로운 배열에 push 해준다.   ->  [ ..., [2] ]

 

const getSubSets = function(arr){
  
  // subSet 함수는 선언되었을 때의 환경 (flag와subSets)을 계속 기억하게된다.
  // 해당 노드 방문 여부를 표시하는 배열
  let flag = new Array(arr.length).fill(false);
  // 부분 집합들을 모아놓는 배열
  const subSets = [];
  
  const subSet = function DFS(depth){
    // BASE CASE
    // 트리의 끝부분에 다다랐을 때 재귀 함수를 종료하고 subSets배열에 push한다.
    if(depth === arr.length){
      const element = arr.filter((_,index) => flag[index]);
      subSets.push(element);
      
      return;
    }
    
    // 트리의 왼쪽 해당 depth는 true
    flag[depth] = true;
    subSet(depth + 1);
    
    // 트리의 오른쪽 해당 depth는 false
    flag[depth] = false;
    subSet(depth + 1);
  }
  
  // subSet 함수 호출 : depth 0부터 시작한다.
  subSet(0);
  // 재귀 호출이 모두 끝나고 부분집합 요소들이 담긴 sunSets 배열을 리턴한다.
  return subSets;
}

 

// 함수 호출
getSubSets([1, 2, 3, 4, 5]);

/* [
      [1, 2, 3, 4, 5],
      [1, 2, 3, 4],
      [1, 2, 3, 5],
      [1, 2, 3],
      [1, 2, 4, 5],
      [1, 2, 4],
      [1, 2, 5],
      [1, 2],
      [1, 3, 4, 5],
      [1, 3, 4],
      [1, 3, 5],
      [1, 3],
      [1, 4, 5],
      [1, 4],
      [1, 5],
      [1],
      [2, 3, 4, 5],
      [2, 3, 4],
      [2, 3, 5],
      [2, 3],
      [2, 4, 5],
      [2, 4],
      [2, 5],
      [2],
      [3, 4, 5],
      [3, 4],
      [3, 5],
      [3],
      [4, 5],
      [4],
      [5],
      []
  ] */

 

트리를 완전 탐색한 결과와 똑~같이 나오는 걸 확인할 수 있다.

 

---

 

const subSets = (arr) => {
  const result = [];
  
  const dfs = (start = 0, subset = []) => {
    result.push(subset);
    
    for(let i=start; i<arr.length; i++){
      dfs(i + 1, [...subset, arr[i]];
    }
  };
  
  dfs();
  
  return result;
};

 

오늘 해야할 일  -->  Udemy DFS 완전 탐색 강의 듣기