[java script] 부분집합 만들기.

완전 탐색 문제? 같은 거를 풀 때, 

우선 주어진 자료를 이용해서 부분집합을 만들어야하는 경우가 있다. 

 

 

부분집합의 개수 :  원소의 개수가 n인 집합의 부분집합의 개수는 2^n, 2의 n승이다.

 

 

첫번째 방법 (for문을 중첩)

위 식을 보면 결국 어떤 원소가 포함되는가? 포함되지 않는가? 에 대한 경우를 따지는 것이다. 

그래서 그걸 이용해서 포함된다면 bit를 1로, 포함되지 않는다면 bit를 0으로 나타낸 다음에 나중에 그 bit를 해석해서 부분집합을 나타내봤다. 

//부분집합만들기. 
//Loop를 이용한 부분집합 생성.
let arr = ['1', '2', '3', '4'];
let bitArray = [];

//첫번째 원소가 부분집합에 포합되면 bit는 1, 아니면 0  
for (let i = 0; i < 2; i++) {
  bitArray[0] = (i == 1) ? 1 : 0;
  //두번째 원소가 부분집합에 포합되면 bit는 1, 아니면 0 
  for (let j = 0; j < 2; j++) {
    bitArray[1] = (j == 1) ? 1 : 0;
    //세번째 원소가 부분집합에 포합되면 bit는 1, 아니면 0 
    for (let k = 0; k < 2; k++) {
      bitArray[2] = (k == 1) ? 1 : 0;
      //네번째 원소가 부분집합에 포합되면 bit는 1, 아니면 0 
      for (let l = 0; l < 2; l++) {
        bitArray[3] = (l == 1) ? 1 : 0;
        let str = '';
        for (let n = 0; n < arr.length; n++) {
          if (bitArray[n] == 1) { //1이면 해당 원소를 추가
            str += arr[n];
          }
        }
        console.log(str);
      }
    }
  }
}

고작 4개의 원소를 가진 집합의 부분집합을 구하는 코드가 꽤 길다.

길지만 별 의미는 없다. 똑같은 for문이 계속 중첩되어 있을 뿐이다.  

원소에 개수가 늘어날 때마다 for문이 하나씩 늘어난다. 

 

 

두번째 방법 (비트연산자를 이용)

비트연산자를 사용해서  코드의 길이를 줄여봤다. 

let arr = ['1', '2', '3', '4'];
let n = arr.length;

for (let i = 0; i < (1 << n); i++) {
  let str = ""
  for (let j = 0; j < n; j++) {
    if (i & (1 << j)) {
      str += arr[j];
    }
  }
  console.log(str);
}

1<<n

<< 비트 연산자는 왼쪽으로 비트를 한칸 이동시키는 연산자다. 

2의 n승을 1<<n로 나타낼 수 있음!  예) 1<<1 은 2,   1<<2 는 4  , 1<<10 은 1024.

 

결국 첫번째 for문의 의미는 부분 집합의 개수만큼 반복한다는 것이다.

 

i & (1 << j)

i의 j번째 bit가 1인지 확인한다.