[알고리즘] 순열 / 중복순열 / 조합 / 중복조합

순열

• 서로 다른 n개 중 r개를 뽑아서 정렬 하는 것
• 즉, 순서가 있어 순서가 다르면 다른 것으로 카운팅함
• AB != AB

// int[] arr : 원본 배열
// int[] out : 출력 배열
// boolean[] visited : 방문체크
// int depth : 현재 탐색중인 인덱스
// int r : 뽑고자 하는 개수

public class 순열 {
    public static void main(String[] args){
        int[] arr = {1, 2, 3};
        int r = 2;
        permutation(arr, new int[r], new boolean[arr.length], 0, r);
    }
    public static void permutation(int[] arr, int[] out, boolean[] visited, int depth, int r){
        if(depth == r){
            for(int num: out){
            	System.out.print(num);
            }
            System.out.println();
            return;
        }
        for(int i=0; i<arr.length; i++){
            if(!visited[i]){
                visited[i] = true;
                out[depth] = arr[i];
                permutation(arr, out, visited, depth+1, r);
                visited[i] = false;
            }
        }
    }
}

---

중복 순열

• 서로 다른 n개 중 중복 가능하게 r개를 뽑아서 정렬 하는 것

// int[] arr : 원본 배열
// int[] out : 출력 배열
// boolean[] visited : 방문체크
// int depth : 현재 탐색중인 인덱스
// int r : 뽑고자 하는 개수

public class 중복순열 {
    public static void main(String[] args){
        int[] arr = {1, 2, 3};
        int r = 2;
        permutation(arr, new int[r], 0, r);
    }
    public static void permutation(int[] arr, int[] out, int depth, int r){
        if(depth == r){
            for(int num: out){
            	System.out.print(num);
            }
            System.out.println();
            return;
        }
		for(int i=0; i<arr.length; i++){
            out[depth] = arr[i];
            permutation(arr, out, depth+1, r);
        }
    }
}

-> 중복이 가능하기 때문에 중복 방지를 위한 방문체크(visited)를 해주지 않아도 됨 

---

조합

• 서로 다른 n개 중 r개를 순서 없이 뽑는 것
• AB == BA

// int[] arr : 원본 배열
// boolean[] visited : 방문 체크
// int start : 탐색 시작 인덱스
// int depth : 현재 탐색중인 인덱스
// int r : 뽑고자 하는 개수

public class 조합 {
    public static void main(String[] args){
        int[] arr = {1, 2, 3};
        int r = 2;
        combination(arr, new boolean[arr.length], 0, 0, r);
    }
    
    public static void combination(int[] arr, boolean[] visited, int start, int depth, int r){
        if(depth == r){
            for(int i=0; i<arr.length; i++){
                if(visited[i]) System.out.print(arr[i]);
            }
            System.out.println();
            return;
        }
        for(int i=start; i<arr.length; i++){
            if(!visited[i]){
                visited[i] = true;
                combination(arr, visited, i+1, depth+1, r);
                visited[i] = false;
            }
        }
    }

}

---

중복조합

• 서로 다른 n개 중 중복 가능하게 r개를 순서 없이 뽑는 것

// int[] arr : 원본 배열
// int[] out : 출력 배열
// int start : 탐색 시작 인덱스
// int depth : 현재 탐색중인 인덱스
// int r : 뽑고자 하는 개수

public class 중복조합 {

	public static void main(String[] args){
        int[] arr = {1, 2, 3};
        int r = 2;
        combination(arr, new int[r], 0, 0, r);
    }
    
    public static void combination(int[] arr, int[] out, int start, int depth, int r){
        if(depth == r){
            for(int num : out) System.out.print(num);
            System.out.println();
            return;
        }
        for(int i=start; i<arr.length; i++){
            out[depth] = arr[i];
            combination(arr, out, i, depth+1, r);
        }
    }
}

---