[알고리즘] 순열, 조합, 부분집합

순열

정의

• 서로 다른 원소 n개의 원소 중 중복 원소를 선택하지 않고, 순서를 고려하여 r개를 일렬로 나열하는 수열
• nPr 개의 집합을 만들 수 있음
  • n 팩토리얼에 (n - r )!을 나눈 만큼의 경우의 수
    • n! / ( n - r )!
    • ex) 5 P 3 = 5 4 3 2 1 / ( 2 * 1 )

구현

• nPr의 순열을 구하기 위해서는 r번의 반복문이 필요하므로, 단순 반복문으로는 구현의 한계가 있음.
• r의 크기를 가진 배열을 모두 채울 때까지 재귀로 반복
• 재귀와 재귀 내의 반복으로 구현하므로 r이 커질수록 시간 복잡도가 급격히 상승함

/** 
 *  idx == 현재 뽑고 있는 인덱스
 *  */
static final SOURCE_NUM = srcArr.length;
static final GET_NUM = resArr.length;
static boolean[] check = new boolean[SOURCE_NUM];
public static void f(int idx) {
    if(idx == GET_NUM) {
        //재귀 기저 조건
        //do something with resArr[]...
        return ;
    }

    for(int i = 0; i < SOURCE_NUM; i++) {
        if(check[i]) continue;

        resArr[idx] = srcArr[i];
        /** 중복 선택이 되지 않도록 마킹 */
        check[i] = true;

        f(idx + 1);
        /** 분기를 마치고 다시 뿌리 메소드에 도착하면 원래대로 되돌림 */
        check[i] = false;
    }
//check 배열 대신 비트마스크로도 사용 가능
}

• 크기 r인 배열에 대해서 첫 번째 인덱스로부터 마지막 인덱스까지 재귀적으로 할당
• 0 ~ r-1 까지의 인덱스에 크기 n인 소스 배열의 모든 인덱스를 넣으면서 재귀 호출
  • 중복을 불허하므로 소스 배열에서 사용된 인자는 check배열을 중복체크함
• r - 1 번째 인덱스까지 할당하여 결과 배열을 채웠을 경우를 기저조건으로 하여 순열의 한 가지를 완성함
• 각 분기별로 사용 체크가 달라지므로, 해당 분기 탐색이 종료되면 check 배열을 원래대로 돌림
• 체크 배열을 정수 값 비트 마스크로도 사용할 수 있다.

중복 순열

• 순열에서 중복 체크를 하지 않음
• 모든 요소를 담을 수 있으므로 n^n 의 시간복잡도

조합

정의

• 서로 다른 원소 n개의 원소 중 중복 원소를 선택하지 않으며 순서를 고려하지 않고 r개를 일렬로 나열하는 수열
• nCr 개의 경우의 수를 갖는다.
  • nCr = nPr / r!

구현

• 수열과 같이 r개의 반복문이 필요하므로 재귀적으로 구현
• r의 크기를 가진 결과 배열을 모두 채울 때까지 재귀
• r의 크기가 커질수록 시간복잡도 크게 증가

/** 
 * 조합 
 * idx 현재 값을 넣을 인덱스 
 * start 중복 제거를 위해 현재까지 지나온 소스배열의 인덱스를 검사하기 위해 넘김
 */
static final SOURCE_NUM = srcArr.length;
static final GET_NUM = resArr.length;
public static void f(int idx, int idxStart) {
    if(idx == GET_NUM) {
        //재귀 기저 조건
        //do something with resArr[] ...
        return ;
    }

    for(int i = idxStart ; i < SOURCE_NUM; i++ ) {
        resArr[idx] = srcArr[i];

        /** 파라미터에 idx+1과 i + 1 을 넣는다, 현재 넣은 값 +1*/
        /** start를 통해 중복점검을 했기 때문에 추가 중복점검은 필요 없다 */
        f2(idx + 1, i + 1);
    }
}

• 크기가 r인 결과 배열에 첫 번째 인덱스로부터 마지막 인덱스까지 재귀적으로 할당
• 0 ~ r-1 까지의 인덱스에 크기 n인 소스 배열의 시작 인덱스부터 값을 넣으면서 재귀 호출
  • 이 때 조합은 순서에 관계 없이 만들어지므로 모든 소스 배열의 값은 한번만 들어가거나 들어가지 않을 수 있다.
  • 그러므로 반복의 시작 인자를 이전에 결과 배열에 넣었던 값보다 1 크게하여 반복한다.
• 반복 인자를 통해 중복을 배제하여 중복검사를 따로 하지 않아도 됨

중복조합

• 일반 조합과 다르게 현재 소스 배열 인덱스가 다시 반복문에서 검사될 수 있도록 i를 그대로 재귀로 넘긴다.

/** 
* 중복 조합 
* idx 현재 값을 넣을 인덱스 
* start 현재 소스배열 인덱스가 다시 들어갈 수 있으므로 i + 1 이 아닌 i를 다음 재귀로 넘김
*/
static final SOURCE_NUM = srcArr.length;
static final GET_NUM = resArr.length;
public static void f(int idx, int idxStart) {
    if(idx == GET_NUM) {
        //재귀 기저 조건
        //do something with resArr[] ...
        return ;
    }

    for(int i = idxStart ; i < SOURCE_NUM; i++ ) {
        resArr[idx] = srcArr[i];

        /** 중복 허용을 위해 넣었던 값을 다시 반복문에서 검사할 수 있도록 i를 그대로 넣음 */
        f2(idx + 1, i);
    }
}

부분집합

• 다수의 중요 알고리즘들이 그룹에서 최적의 부분 집합을 찾는 것
• 집합의 원소가 n개 일 때 공집합 포함 부분집합 개수는 2^n개

구현

• 각 원소를 선택하거나 선택하지 않은 두 조건으로 분기
  • 이진 트리의 꼴로 재귀함
• 해당 원소가 선택됐든 안됐든 그 원소에 대한 처리는 한번만 하므로 중복의 경우가 없음.

public static int[] arr = new int[N];
public static boolean[] isSelected = new boolean[N];
public static void f(int idx) {
    if(idx == N) {
      //기저조건
      for(int i = 0 ; i < idx ; i++) {
        if(isSelected[i])	sb.append(arr[N]);
      }
      return ;
    }

    /** 
     * 선택된 경우와 안선택된 경우의 분기, (이진 트리) 
     * 다시 되돌릴 필요가 없음 -> 사용하기 전에 마킹을 그에 맞게함 
     * 즉 매 반복마다 선택을 했는지 안했는지에 따라 행동을 달리하지 않음.
     * 골랐다와 안골랐다
     */
    isSelected[idx] = true;
    f(idx + 1);

    isSelected[idx] = false;
    f(idx + 1);
}

• 인덱스마다 해당 원소의 선택 여부에 따라 두 가지로 재귀 호출한다
  • 이 때 선택 여부를 체크 배열의 값으로 확인한다.
  • 매 분기의 시작에 해당 인덱스의 선택여부를 다시 할당하므로 분기가 끝나고 되돌려 줄 필요 없음
• 기저 조건에서 체크 배열로 어떤 원소가 선택 되었는 지에 따라 동작
• 체크 배열을 정수값 비트마스크로 사용할 수 있다.