순열

n개의 원소에서 순서를 생각하며 r개의 원소를 선택하는 방법이다.
순서를 생각하며 뽑는 방법이기 때문에 뽑은 원소의 구성이 같더라도 순서를 다르게해서 뽑혔으면 다른 경우의 수가 된다.

입력 : [1, 2, 3]
출력 : [1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 2, 1], [3, 1, 2]

Java (Swap을 이용한 방법)

이 방법의 경우는 n개에서 r개를 선택한다기 보다, 위치를 변경하여 뽑은것과 같은 효과를 주기 위함이다.

public void swap(int idx, int idx2, int[] arr){
	int tmp = arr[idx];
	arr[idx2] = arr[idx];
    arr[idx2] = tmp;
}

// n개의 원소 중, r개의 원소를 순서를 생각하며 뽑는 방법
public void permutation(int depth, int r, int[] arr){
	if(depth == r){
    	// r개를 모두 뽑음
        for(int i = 0; i<r; i++){
        	System.out.print(arr[i] + " ");
        }
        return;
    }
    
    for(int i = depth; i < arr.length; i++){
    	// 위치를 바꿔 원소가 선택되었음을 나타낸다.
    	swap(i, depth, arr);
        permutation(depth + 1, r, arr);
        // 다시 원래대로 바꿔서 다른 시행에 영향이 가지 않도록 한다.
        swap(i, depth, arr);
    }
}

Java (재귀함수를 이용한 방법)

swap을 이용하여 순열을 구현할 경우, 원본 배열에 영향을 주지 않는다는 점이 장점이다. 하지만, 구현이 어렵기 때문에 다음과 같이 반복문을 사용해도 된다.

/* 
 * visit 배열은 원본 배열에서 고른 원소를 마킹하기 위한 배열이며, 
 * visit배열과 arr배열의 크기는 같다.
 * idx는 원본 배열(arr)의 인덱스를 나타낸다.
**/
public static void permutation_Recur(boolean[] visit, int idx, int[] arr, int sidx, int[] sel, int r) {
    // r개를 뽑음
    if (sidx == r) {
      ArrayList<Integer> list = new ArrayList<Integer>();
      for (int i = 0; i < visit.length; i++) {
        if (visit[i])
          list.add(sel[i]);
      }

      System.out.println(list);
      return;
    }

    if (idx == r) {
      return;
    }

    for (int i = 0; i < arr.length; i++) {
      if (!visit[i]) {
      	/*
         * arr[i]를 선택했음을 표시하고, 결과 배열에 넣음으로써
         * arr[i]가 중복되서 선택되는 것을 방지하고, 고르는 순서를 유지
         **/
        visit[i] = true;
        sel[sidx] = arr[i];
        permutation_Recur(visit, idx + 1, arr, sidx + 1, sel, r);
        visit[i] = false; // 다음 시행을 위한 제거
      }
    }
  }

조합

순열과 같이 n개의 원소에서 r개의 원소를 선택하지만, 원소를 뽑는 순서는 고려하지 않는다.
즉, 다른 두 경우의 수가 있을 때, 두 경우의 수의 내용(뽑은 원소)가 같다면 같은 경우의 수로 생각한다.

뽑는 순서는 고려하지 않으므로, 해당 원소를 뽑는지 안뽑는지만 생각하면 된다. 부분집합과 다른점은, 무조건 r개를 뽑아야 한다는 것이다.

$_{3} \mathrm{C}_2$ 를 구한다고 하면 입력과 출력은 다음과 같다.

입력 : [1, 2, 3]
출력 : [1, 2], [1, 3], [2, 3]

Java

/*
 * 원본 배열(arr)의 길이 : n
 * 선택 배열(select)의 길이 : r
 * 선택 여부를 저장할 배열(visit)의 길이 : n
**/
public static void combination(int[] arr, int idx, int sidx, int[] sel, int r) {
	// r개를 뽑았을 경우에만 결과물을 출력
    if (sidx == r) {
      List<Integer> list = new ArrayList<>();
      for (int i = 0; i < r; i++) {
        list.add(sel[i]);
      }
      System.out.println(list);
      return;
    }

    // 기저 조건
    if (idx == arr.length) {
      return;
    }

    combination(arr, idx + 1, sidx, sel, r);  // 선택 안함
    sel[sidx] = arr[idx];
    combination(arr, idx + 1, sidx + 1, sel, r);  // 선택 함
  }

부분 집합(Power Set)

부분 집합은 집합의 원소 일부로 이루어진 집합을 의미하며, 자기 자신도 부분집합이 될 수 있으며, 원소가 전혀 없는 공집합($\emptyset$)도 부분집합이다.
그렇기 때문에, 각각의 원소를 선택하는 경우, 선택하지 않는 경우 두 가지의 경우로 나뉘며 전체 Big-O 시간은 $O(2^n)$이 된다.

조합과 다른점은, 조합은 r개를 선택하는 경우의 수 이지만, 부분집합은 선택하는 수가 0~n까지 다양하기 때문에 원본 배열을 모두 돌아보면 고른것들을 그대로 출력한다.

그래서 아래 예제와 같이 select배열을 써서 따로 저장해도 되지만, boolean[] 배열을 통해 선택 여부만 체크하고 넘어가서 배열의 원소가 true일 경우에 결과배열에 넣어도 된다.

입력 : [1, 2, 3]
출력 : [], [1], [2], [3], [1, 2], [1, 3], [2, 3], [1, 2, 3]

Java

  public static void subset(int[] arr, int idx, int[] select, int sidx) {
  	// r개를 고르지 않아도, 원본 배열을 모두 돌았으면 출력
    if (idx == arr.length) {
      ArrayList<Integer> list = new ArrayList<>();

      for (int i = 0; i < sidx; i++) {
        list.add(select[i]);
      }
      System.out.println(list);
      return;
    }

    subset(arr, idx + 1, select, sidx);
    select[sidx] = arr[idx];
    subset(arr, idx + 1, select, sidx + 1);
  }

Java - Bitmask 이용

재귀 함수를 이용하여 선택할 수도 있지만, bitmask를 이용하여 구할 수 도 있다.

public static void subset_bitmask(int[] arr) {
    // 1 << arr.length : arr배열로부터 나올 수 있는 PowerSet의 개수
    for (int i = 0; i < 1 << arr.length; i++) {
      ArrayList<Integer> list = new ArrayList<>();
      for (int j = 0; j < arr.length; j++) {
        if ((i & 1 << j) != 0) {
          list.add(arr[j]);
        }
      }
      System.out.println(list);
    }

  }