[이때안] 순열, 중복 순열, 조합, 중복 조합(JAVA)

 

순열 Permutation

1~4까지의 자연수 4개의 숫자 중 2개를 뽑을 때, [1,2] [2,1]이 서로 다른 것으로 간주된다.

[1,1] 과 같이 중복 선택은 안되기 때문에 visited 변수로 이전에 선택된 것을 구분한다.

 

code

depth는 현재 돌고 있는 인덱스이고,

4(N)개의 숫자 중 2(M)개를 뽑는 것이기 때문에 model 안의 원소가 2개가 채워졌을 때 print 한다.

public class nmSol {
	
    static int[] model;
    static boolean[] visited;
    static int N, M;
	
	public static void permutation(int depth) {
		// 4개 중 2개 뽑는다. [1,2] [2,1]은 서로 다른 거
		if(depth == M) {
			for(int i = 0; i < M; i++) {
				System.out.print(model[i]);
				System.out.print(" ");
			}
			System.out.println();
			return;
		}
		
		for(int i = 0; i < N; i++) {
			if(!visited[i]) {
				visited[i] = true;
				model[depth] = i + 1;
				permutation(depth + 1);
				
				visited[i] = false;
			}
		}
		
	}
	

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

            StringTokenizer st = new StringTokenizer(br.readLine());

            N = Integer.parseInt(st.nextToken());
            M = Integer.parseInt(st.nextToken());

    		model = new int[M];
    		visited = new boolean[N];
            // 순열
            permutation(0);
	}

}

 

 

중복 순열  

순열과 동일하게 [1,2] [2,1]이 서로 다른 것으로 간주된다.

그러나 [1,1]과 같은 중복 선택도 허용되기 때문에 visited 변수를 사용하지 않는다.

 

code

순열 코드에서 visited 관련 코드만 제외한다.

public class nmSol {
	
    static int[] model;
    static int N, M;
	
    public static void dupPermutation(int depth) {
        // 4개 중 2개 뽑는다. [1,2] [2,1]은 서로 다른 거
        if(depth == M) {
            for(int i = 0; i < M; i++) {
                System.out.print(model[i]);
                System.out.print(" ");
            }
            System.out.println();
            return;
        }

        for(int i = 0; i < N; i++) {
                model[depth] = i + 1;
                permutation(depth + 1);
        }

    }

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

            StringTokenizer st = new StringTokenizer(br.readLine());

            N = Integer.parseInt(st.nextToken());
            M = Integer.parseInt(st.nextToken());

            model = new int[M];

            // 중복 순열
            dupPermutation(0);
    }

}

 

조합 Combination

1~4까지의 자연수 4개의 숫자 중 2개를 뽑을 때, [1,2] [2,1]이 서로 같은 것으로 간주된다.

[1,1] 과 같이 중복 선택은 안된다.

 

code

순열에서는 중복을 구분하기 위해 visited 변수를 썼지만,

여기선 백트래킹의 start index 조건이 추가되었기 때문에 visited 변수는 따로 사용하지 않았다.

 

조합에서는 백트래킹을 할 때 시작점이 다시 처음부터 가면 안되기 때문에

for문으로 돌 때 i의 start index를 지정해 주어야 한다.

 

예를 들어 [1,2] [1,3] [1,4] 출력 후 첫번째 인덱스가 2인 것으로 트래킹할 때

[2,1]부터 다시 도는 것이 아닌 [2,3] [2,4]를 돌아야 한다.

public class nmSol {
	
    static int[] model;
    static int N, M;
	
    public static void combination(int startInd, int depth) {
        // 4개 중 2개 뽑는다. [1,2] [2,1]은 서로 같은 거
        if(depth == M) {
            for(int i = 0; i < M; i++) {
                System.out.print(model[i]);
                System.out.print(" ");
            }
            System.out.println();
            return;
        }

        for(int i = startInd; i < N; i++) {
            model[depth] = i + 1;
            combination(i + 1, depth + 1); // startInd가 그 이전 i보다 작으면 안되기 때문에 i+1을 넘겨줌
        }

    }

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

            StringTokenizer st = new StringTokenizer(br.readLine());

            N = Integer.parseInt(st.nextToken());
            M = Integer.parseInt(st.nextToken());

            model = new int[M];

            // 조합
            combination(0,0);
    }

}

 

 

중복 조합

1~4까지의 자연수 4개의 숫자 중 2개를 뽑을 때, [1,2] [2,1]이 서로 같은 것으로 간주된다.

[1,1] 과 같이 중복 선택이 허용된다.

 

code

순열에서는 중복 허용 여부에 따라 visited 변수를 썼지만

조합에서는 백트래킹의 start index를 조정하는 것으로 해결할 수 있다.

package NM;

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

public class nmSol {
	
    static int[] model;
    static int N, M;
	
    public static void dupCombination(int startInd, int depth) {
        // 4개 중 2개 뽑는다. [1,2] [2,1]은 서로 같은 거
        if(depth == M) {
            for(int i = 0; i < M; i++) {
                System.out.print(model[i]);
                System.out.print(" ");
            }
            System.out.println();
            return;
        }

        for(int i = startInd; i < N; i++) {
            model[depth] = i + 1;
            combination(i, depth + 1); 
        }

    }


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

            StringTokenizer st = new StringTokenizer(br.readLine());

            N = Integer.parseInt(st.nextToken());
            M = Integer.parseInt(st.nextToken());

            model = new int[M];
            // 중복 조합
            dupCombination(0,0);
    }

}

 

 

순열과 조합의 차이는 for 문에서 i를 어떻게 설정하는지에 따라 구분된다.

i가 곧 model의 요소가 되기 때문에 백트래킹을 처음부터 다시 돌 지, 그 이후부터 돌지를 결정하는 요소이기 때문이다. 

 

depth는 현재 model의 몇 번째 인덱스를 돌고 있는지, i는 그 값이라고 생각하자.