조합과 파워셋

11 Feb 2020 in Study on algo

조합

서로 다른 n개 중에서 r개 취하여 조를 만들 때, 이 하나하나의 조를 n개 중에서 r개 취한 조합

- 소스코드

import java.util.Arrays;
public class 조합 {
       public static void main(String[] args) {
              combination(new int[] { 1, 2, 3 }, new int[2], 0, 0);
       }

       static void combination(int[] arr, int[] sel, int idx, int cnt) { 
              if (cnt == sel.length) {
                     System.out.println(Arrays.toString(sel));
                     return;
              }
              if (idx == arr.length)
                     return;
              sel[cnt] = arr[idx];
              combination(arr, sel, idx + 1, cnt + 1);
              combination(arr, sel, idx + 1, cnt);
       }

- 결과

[1, 2]
[1, 3]
[2, 3]

파워셋

거듭제곱 집합 멱집합: 주어진 집합의 모든 부분집합들을 원소로 가지는 집합

1. 모든 부분 집합

- 소스코드

import java.util.Arrays;
public class 파워셋 {
       public static void main(String[] args) {
              int[] arr = { 1, 2, 3, 4 };
              powerset(arr, new boolean[4], 0);
       }

       static void powerset(int[] arr, boolean sel[], int idx) {
              if (idx == arr.length) {
                     for (int i = 0; i < arr.length; i++) {
                           if (sel[i])
                                  System.out.print(arr[i]+" ");
                     }
                     System.out.println();
                     return;
              }
              sel[idx] = false;
              powerset(arr, sel, idx + 1);
              sel[idx] = true;
              powerset(arr, sel, idx + 1);
       }
}

- 결과

  // 모두 false 인 경우


3 

3 
2 
2 3 

2. 응용) 부분집합의 갯수가 2인 결과만

- 소스코드

import java.util.Arrays;
public class 파워셋 {
       public static void main(String[] args) {
              int[] arr = { 1, 2, 3 };
              powerset2(arr, new boolean[4], 0, 0);
       }
       
       static void powerset2(int[] arr, boolean sel[], int idx, int cnt) {
              if (idx == arr.length) {
                     if (cnt == 2) {
                           for (int i = 0; i < arr.length; i++) {
                                  if (sel[i])
                                         System.out.print(arr[i]+" ");
                           }
                           System.out.println();
                     }
                     return;
              }
              sel[idx] = false;
              powerset2(arr, sel, idx + 1, cnt);
              sel[idx] = true;
              powerset2(arr, sel, idx + 1, cnt +  1);
       }
}

- 결과

3 
3 
2 