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

순열 ( nPr )

static int N, R;
static int[] input, numbers;
public static void permutation(int cnt, int flag) { // cnt: 직전까지 뽑은 수개수, flag: 뽑힌 수들에 대한 플래그 비트열
    if(cnt == R) {
        System.out.println(Arrays.toString(numbers));
        return;
    }

    // 입력받은 모든 수를 현재 자리에 넣어보기
    for (int i = 0; i < N; i++) {
        if((flag&(1<<i)) != 0) continue;	// 기존자리의 수들과 중복되는지 체크
        numbers[cnt] = input[i];
        permutation(cnt+1, flag|(1<<i));	// 다음수 뽑으러 가기
    }
}

 

중복 순열 ( nPir )

static int N, R;
static int[] input, numbers;
public static void permutationWithRepetition(int cnt) {
    if(cnt>=R) {
        System.out.println(Arrays.toString(numbers));
        return;
    }

    for(int i=0; i<N; i++) {
        numbers[cnt] = input[i];
        permutationWithRepetition(cnt+1);
    }
}

 

조합 ( nCr )

static int N, R;
static int[] input, numbers;
public static void combination(int cnt, int start) {
    if(cnt == R) {
        System.out.println(Arrays.toString(numbers));
        return;
    }
    for (int i = start; i < N; i++) {
        numbers[cnt] = input[i];
        combination(cnt+1, i+1); // 다음자리는 현재 뽑은 i의 다음수부터 시작하도록 전달
    }
}

 

중복 조합 ( nHr )

static int N, R;
static int[] input, numbers;
public static void combinationWithRepetition(int cnt, int start) {
    if(cnt>=R) {
        System.out.println(Arrays.toString(numbers));
        return;
    }

    for(int i=start; i<N; i++) {
        numbers[cnt] = input[i];
        combinationWithRepetition(cnt+1, start);
    }
}

 

부분집합 ( subset )

static int N,R;
static int[] input, numbers;
public static void generateSubset(int cnt) { // 부분집합에 고려해야 하는 원소, 직전까지 고려한 원소 수
    if(cnt==N) { // 마지막 원소까지 부분집합에 다 고려된 상황
        for (int i = 0; i < N; i++) {
            System.out.print((isSelected[i]?input[i]:"X")+" ");
        }
        System.out.println();
        return;
    }

    // 현재 원소를 선택
    isSelected[cnt] = true;
    generateSubset(cnt+1);

    // 현재 원소를 비선택
    isSelected[cnt] = false;
    generateSubset(cnt+1);
}