[Java] 순열과 조합

 

 

종류	설명	기호	시간복잡도
순열	N개의 원소 중 R개의 원소로 순서를 가진 부분집합을 만드는 경우의 수	nPr	O(N!)
조합	N개의 원소 중 R개의 원소로 부분집합을 만드는 경우의 수	nCr	O(n! / (r! x (n-r)!))
부분집합	N개의 원소로 부분집합을 만드는 모든 경우의 수	nHr	O(2^N)

 

---

1. 순열

 

가. 반복문

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Permutation {

    static int N, R=3;
    static int[] map, ret;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int TC = Integer.parseInt(st.nextToken());

        for(int tc=1; tc<=TC; tc++) {
            st = new StringTokenizer(br.readLine());
            N = Integer.parseInt(st.nextToken());
            map = new int[N];
            ret = new int[R];

            //input
            st = new StringTokenizer(br.readLine());
            for(int i=0; i<N; i++) {
                map[i] = Integer.parseInt(st.nextToken());
            }

            //make permutation
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    for (int k = 0; k < N; k++) {
                        if (i != j && i != k && j != k) {
                            ret[0] = map[i];
                            ret[1] = map[j];
                            ret[2] = map[k];
                            System.out.println(Arrays.toString(ret));
                        }
                    }
                }
            }
        }
    }
}

nPr에서 r이 고정되어 있고, 일반적으로 3중 for문을 넘지 않는 경우.

 

---

나. 재귀함수

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Permutation {

    static int N, R;
    static int[] map, ret;
    static boolean[] visited;

    public static void perm(int idx) {
        if(idx==R) {
            System.out.println(Arrays.toString(ret));
            return;
        }

        // operation & recursive call
        for(int i=0; i<N; i++) {
            // already exists?
            if(visited[i]) continue;

            ret[idx] = map[i];
            visited[i] = true;
            perm(idx + 1);

            // recover
            //ret[idx] = 0;
            visited[i] = false;
        }
        return;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int TC = Integer.parseInt(st.nextToken());

        for(int tc=1; tc<=TC; tc++) {
            st = new StringTokenizer(br.readLine());
            N = Integer.parseInt(st.nextToken());
            R = Integer.parseInt(st.nextToken());
            map = new int[N];
            ret = new int[R];
            visited = new boolean[N];

            //input
            st = new StringTokenizer(br.readLine());
            for(int i=0; i<N; i++) {
                map[i] = Integer.parseInt(st.nextToken());
            }

            //make permutation
            perm(0);
        }

    }

}

시간 복잡도는 O(N!)이다.

 

---

다. next permutation

 

[Java] 비트 마스킹, Next_Permutation

 

---

라. swap

 

C++이지만 swap으로 순열을 만드는 방법 참고.

[C++] 순열

 

---

2. 조합

 

가. 반복문

for i from 1 to 4
    for j from i+1 to 4
        for k from j+1 to 4
            print i, j, k
        end for
    end for
end for

3차원까지만 반복문으로 구현하자.

 

---

나. 재귀함수

//nCr
int end = n;
int[] numbers = new int[r];
comb(int cnt, int start){
    if(cnt == r) {
        System.out.println(numbers);
        return;
    }
    for(int i=start; i<=end; ++i){
        numbers[cnt] = i;
        comb(cnt+1, i+1);
    }
}

import java.util.Scanner;
import java.util.Arrays;

public class DiceTest {

    static int N;
    static int[] numbers;
    static boolean[] isSelected;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt(); // 주사위 던지는 횟수
        numbers = new int[N];
        int mode = sc.nextInt(); // 주사위 던지기 모드
        switch (mode) {
        case 1 : // 중복 순열
            dice1(0);
            break;
        case 2 : // 순열
            isSelected = new boolean[7];
            dice2(0);
            break;
        case 3: // 중복 조합
            dice3(0, 1);
            break;
        case 4 : // 조합
            dice4(0, 1);
            break;
        }
        sc.close();
    }

    public static void dice1(int cnt){
        if(cnt == N){
            System.out.println(Arrays.toString(numbers));
            return;
        }
        for(int i=1; i<=6; i++){
            //if(isSelected[i]) continue;
            numbers[cnt]=i;
            //isSelected[i] = true;
            dice1(cnt+1);
            //isSelected[i] = false;
        }
    }

    public static void dice2(int cnt){
        if(cnt == N){
            System.out.println(Arrays.toString(numbers));
            return;
        }
        for(int i=1; i<=6; i++){
            if(isSelected[i]) continue;
            numbers[cnt]=i;
            isSelected[i] = true;
            dice2(cnt+1);
            isSelected[i] = false;
        }
    }

    public static void dice3(int cnt, int start) {
        if(cnt==N) {
            System.out.println(Arrays.toString(numbers));
            return;
        }

        for(int i=start; i<=6; i++) {
            numbers[cnt]=i;
            dice3(cnt+1, i); // 현재 선택한 수부터 선택
        }
    }
    public static void dice4(int cnt, int start) {
        if(cnt==N) {
            System.out.println(Arrays.toString(numbers));
            return;
        }

        for(int i=start; i<=6; i++) {
            numbers[cnt]=i;
            dice4(cnt+1, i+1); // 현재 선택한 수의 다음부터 선택
        }
    }

}

 

---