[알고리즘]순열, 조합, 부분집합 - Java로 구현하기

📖순열, 조합, 부분집합

1. 순열(Permutation)

: 순서에 따라 배열된 원소들의 모든 가능한 조합(순서 O, 중복 X) - 주어진 원소들을 나열하는 경우의 수 계산

2. 조합(Combination)

: 순서에 상관없이 선택된 원소들의 모든 가능한 조합(순서X, 중복X) - 주어진 원소들을 뽑는 경우의 수 계산

3. 부분집합(Subset)

: 어떤 집합의 일부 원소로 이루어진 집합 - 주어진 집합의 모든 부분집합 계산

 

🔍순열 구현

1. 중복원소를 boolean 배열을 이용해서 확인

import java.util.Arrays;

// 중복 원소를 배열을 이용해서 체크하기 
// 9P9   : 0.01	    	(안전)
// 10P10 : 0.1초 컷		(약간 위험) 
public class PermutationTest_flag {
    static int N,R; //nPr
    static int[] numbers; //기존 data
    static int[] perms; //내가 만든 순열 조합
    static boolean[] isSelected; //배열을 이용해서 중복 원소 관리
    ////////////count
    static long tc; //순열 개수
    static long cnt; //반복 횟수

    public static void perm(int depth){
        if(depth>=R){
            tc++;
            //System.out.println(Arrays.toString(perms));
            return;
        }

        for(int i=0;i<N;i++){
            cnt++;
            if(isSelected[i]) continue;
            perms[depth]=i;
            isSelected[depth]=true;
            perm(depth+1);
            isSelected[depth]=false;
        }
    }

    public static void main(String[] args){
        numbers = new int[] {1,2,3,4,5,6,7,8,9,10};
        N = numbers.length;
        R = numbers.length;
        perms = new int[R];
        isSelected = new boolean[N];

        long start = System.currentTimeMillis();
        perm(0);
        long end = System.currentTimeMillis();
        System.out.printf("tc: %d   count:%d   time:%dms%n", tc, cnt, end-start);
    }
}

 

2. 중복원소를 비트마스킹을 이용해서 확인

import java.util.Arrays;

// 중복 원소를 bitmask를 이용해서 체크하기
// 9P9   : 0.009	    (안전)
// 10P10 : 0.1초 컷		(약간 위험)     tc: 3628800   count:62353010   time:173ms
public class PermutationTest_bitmasking {
    static int N,R; //nPr
    static int[] numbers; //기존 data
    static int[] perms; //내가 만든 순열 조합
    static int bitmasking; //비트마스킹을 이용한 중복 원소 관리
    ////////////count
    static long tc; //순열 개수
    static long cnt; //반복 횟수

    public static void perm(int depth){
        if(depth>=R){
            tc++;
            //System.out.println(Arrays.toString(perms));
            return;
        }

        for(int i=0;i<N;i++){
            cnt++;
            if((bitmasking & (1<<i))!=0) continue;
            perms[depth]=i;
            bitmasking |= (1<<i);
            perm(depth+1);
            bitmasking &= ~(1<<i);
        }
    }

    public static void main(String[] args){
        //numbers = new int[] {1,2,3};
        numbers = new int[] {1,2,3,4,5,6,7,8,9,10};
        N = numbers.length;
        R = numbers.length;
        perms = new int[R];
        bitmasking = 0;

        long start = System.currentTimeMillis();
        perm(0);
        long end = System.currentTimeMillis();
        System.out.printf("tc: %d   count:%d   time:%dms%n", tc, cnt, end-start);
    }
}

 

3. swap 순열

- 배열의 첫 값부터 순서대로 하나씩 바꾸며 모든 값을 한번씩 swap한다.

- depth를 기준 인덱스로 하여 depth보다 작은 값들은 그대로 고정하고 depth 이상의 인덱스들만 swap을 진행한다.

import java.util.Arrays;

// 10P10 : 0.02초 컷		(안전) tc: 3628800   count:0   time:47ms
public class PermutationTest_swap {
    static int N,R; //nPr
    static int[] numbers; //기존 data
    ////////////count
    static long tc; //순열 개수
    static long cnt; //반복 횟수

    public static void perm(int depth){
        if(depth>=R){
            tc++;
            //System.out.println(Arrays.toString(numbers));
            return;
        }

        for(int i=depth;i<N;i++){
            swap(depth, i);
            perm(depth+1);
            swap(depth, i);
        }
    }

    public static void swap(int i, int j){
        int tmp = numbers[i];
        numbers[i] = numbers[j];
        numbers[j] = tmp;
    }

    public static void main(String[] args){
        //numbers = new int[] {1,2,3};
        numbers = new int[] {1,2,3,4,5,6,7,8,9,10};
        N = numbers.length;
        R = numbers.length;

        long start = System.currentTimeMillis();
        perm(0);
        long end = System.currentTimeMillis();
        System.out.printf("tc: %d   count:%d   time:%dms%n", tc, cnt, end-start);
    }
}

 

4. Next Permutation으로 순열 구현

순열을 사전순으로 나열할 때, 현재 순열의 다음으로 오는 순열을 찾는 알고리즘

1) 뒤쪽부터 탐색하여 p[i-1]<p[i]를 만족하는 가장 큰 i값 찾기. 이때, i=0이면 탐색종료

2) 뒤쪽부터 탐색하여 p[i-1]<p[j]를 만족하는 가장 큰 j값을 찾아 swap

3) index i~N까지 swap

=>반복

Next Permutation은 구현이 어렵지만, O(N)의 시간복잡도를 가지며 구현도 직관적이고 이해하기 쉽다.

import java.util.Arrays;

// 10P10 : 0.02초 time : 29ms   count:5880473   tc:3628800
// 11P11 : 0.15초컷    (위험)
public class Permutation_NP {
    static int[] numbers; //기존 data
    ////////////count
    static long tc=0; //순열 개수
    static long cnt=0; //반복 횟수

    public static boolean np(int[] p){
        int N = p.length-1;

        int i = N;
        while(i>0 && p[i-1]>=p[i]){
            //가장 큰 p[i]<p[i+1]를 찾기
            cnt++;
            --i;
        }
        if(i==0) return false;

        int j = N;
        while(p[i-1]>p[j]){
            cnt++;
            --j;
        }
        swap(p,i-1,j);

        int k = N;
        while(i<k){
            cnt++;
            swap(p,i++,k--);
        }

        return true;
    }

    public static void swap(int[] p, int i, int j){
        int tmp = p[i];
        p[i] = p[j];
        p[j] = tmp;
    }

    public static void main(String[] args){
        numbers = new int[] {1,2,3,4,5,6,7,8,9,10};

        long start = System.currentTimeMillis();
        do{
            tc++;
            //System.out.println(Arrays.toString(numbers));
        }while(np(numbers));
        long end = System.currentTimeMillis();
        System.out.printf("time : %dms   count:%d   tc:%d%n", end-start, cnt, tc);
    }
}

 

🔍조합 구현

import java.util.Arrays;

/**
 * 25C12,13		=> 35ms		안전 조합수 : 5,200,300
 * 26C8			=> 110ms   	위험	조합수 : 10,400,600  ==> 백트레킹을 시도
 * 27C14		=> 241ms	위험	==> 백트레킹을 시도
 * 30C15  		=> 1.2초 컷  안됨 1억 5천
 */
public class CombinationTest {
    static int N,R; //nCr
    static int[] numbers; //기존 data
    static int[] combis; //내가 뽑은 조합
    ////////////count
    static long tc=0; //조합 개수
    static long cnt=0; //반복 횟수

    public static void combi(int depth, int start){
        if(depth>=R){
            tc++;
            //System.out.println(Arrays.toString(combis));
            return;
        }

        for(int i=start;i<N;i++){
            cnt++;
            combis[depth]=i;
            combi(depth+1,i+1);
        }
    }

    public static void main(String[] args){
        N = 26;
        R = 13;
        numbers = new int[N];
        for(int i=0;i<N;i++) numbers[i] = i;
        combis = new int[R];

        long start = System.currentTimeMillis();
        combi(0,0);
        long end = System.currentTimeMillis();
        System.out.printf("time : %dms   count:%d   tc:%d%n", end-start, cnt, tc);
    }
}

 

🔍부분집합 구현

// 25powser :  75ms		경우의 수 : 33,554,432
// 총 경우의 수 : 33554432  time:146
// 26powser :  140ms	경우의 수 : 67,108,863			위험 => BT 필요
// 총 경우의 수 : 67108864  time:290
public class SubsetTest {
    static int N; //data length
    static int[] numbers; //기존 data
    static boolean[] isSelected; //내가 뽑은 부분집합
    ////////////count
    static long tc=0; //부분집합 개수

    public static void subset(int depth){
        if(depth>=N){
            tc++;
            //for(int n : numbers) System.out.print((char)(n+'a')+" ");
            //System.out.println();
            return;
        }

        // 부분집합에 현재 원소를 선택
        isSelected[depth]=true;
        subset(depth+1);
        isSelected[depth]=false;
        // 부분집합에 현재 원소를 선택 X
        subset(depth+1);
    }

    public static void main(String[] args){
        N = 25;
        numbers = new int[N];
        for(int i=0;i<N;i++) numbers[i]=i;
        isSelected = new boolean[N];

        long start = System.currentTimeMillis();
        subset(0);
        long end = System.currentTimeMillis();
        System.out.printf("총 경우의 수 : %d  time:%d%n",tc, end-start);
    }
}

 

 

 

 

 

 

기죽지 말장 ..! 화이팅🥹