[CS지식 - 알고리즘] 순열과 조합

1. 순열

• 길이가 n인 배열에서 r개의 요소를 차례대로 뽑아 배열을 만들었을 때, 가능한 모든 배열(중복제외)
  ▶순열, 중복순열, 조합, 중복조합은 모두 n개에서 r를 뽑다는다는 점에서 동일
• 특징 : 정렬 순서가 있음

1-1. Visited 배열 이용

 static void permutation(int[] arr, int[] out, boolean visited[], int depth, int n, int r){
//arr[] : 뽑고자 하는 배열
    //out[] : 출력결과가 저장되는 배열
    //visited[] : 배열의 방문 여부 체크
    //depty : 현재 탐색하고 있는 인덱스
    //n: 배열의 길이
    //r : 뽑고자 하는 순열의 갯수
            if(depth == r){
	            System.out.println(out,r);
	            return;
	        }
	        for(int i=0; i<n; i++){
	            if(!visited[i]){
	                visited[i] = true;
	                out[depth] = arr[i];
	                permutation(arr, out, visited, depth+1, n, r);
	                visited[i] = false;
	            }
	        }
	    }

 

 

 

1-2. swap 함수이용

static void permutation(int arr[], int current, int n, int r) {
    //arr[] : 뽑고자 하는 배열
    //current : 현재 탐색하고 있는 인덱스
    //n : 배열의 길이
    //r : 뽑고자 하는 순열의 갯수
		if(current ==r) {
			System.out.println(arr,r);
			return;
		}
		for(int i = current; i<n; i++) {
			swap(arr, current,i);
			permutation(arr, current+1, n, r);
			swap(arr, current,i);
		}
	}
	
	static void swap(int arr[], int current, int i) {
		int temp = arr[current];
		arr[current]=arr[i];
		arr[i]=temp;
	}

 

2. 중복 순열

• 서로 다른 n개에서 중복이 가능하게 r개를 뽑아서 정렬하는 경우의 수
• 순열과 공통점 : 순서가 있음
• 순열과 차이점 : 같은 원소를 중복해서 뽑을 수 있음

public class AlgorithmStudy {
    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);
        }
    }

    public static void main(String[] args){
        int[] arr = {1, 2, 3};
        int r = 2;
        permutation(arr, new int[r], 0, r);
    }
}

→ 결과 :  1 1 / 1 2 / 1 3 /  2 1 / 2 2 / 2 3 / 3 1 / 3 2 / 3 3

 

3. 조합

• 서로 다른 n개에서 순서에 상관없이 r개를 뽑는 경우의 수 (중복제외)
  ▶[1, 2]와 [2, 1]을 같은 것으로 취급 이경우 [1, 2]만 카운팅 됨
• 특징 - 순서 상관없음
          - 중복 없음
            ▶ 선택된 원소를 따로 저장하지 않고 원소들과 visited만 이용
            ▶ 방문한 원소들을 순서대로 확인하면 곧 선택된 조합

 static void combination(int[] arr, boolean[] visited, int start, int depth, int n, int r){
//arr[] : 뽑고자 하는 배열
//visited[] : 배열의 방문 여부 체크
//start :현재 탐색하고 있는 인덱스
//n: 배열의 길이
//r : 뽑고자 하는 조합의 갯수
        if(r == 0){
            System.out.println(arr, visited, n);
            return;
        }
        for(int i=start; i<n; i++){
            if(!visited[i]){
                visited[i] = true;
                combination(arr, visited, i+1, n, r-1);
                visited[i] = false;
            }
        }

        static void print(int arr[], boolean visited[], int n) {
            for(int i =0; i<n;i++) {
                if(visited[i]) {
                    System.out.print(arr[i]+" ");
                }
            }
            System.out.println();
    }

4. 중복조합

• 서로 다른 n개에서 순서없이, 중복이 가능하게 r개를 뽑느 경우의 수
• 조합과의 공통점 : 순서 없이 뽑음
• 조합과의 차이점 : 중복 가능

public class AlgorithmStudy {
    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);
        }
    }

    public static void main(String[] args){
        int[] arr = {1, 2, 3};
        int r = 2;
        combination(arr, new int[r], 0, 0, r);
    }
}

결과 → 1 1 / 1 2 / 1 3 / 2 2 / 2 3 / 3 3

 

 

 

 

참고)

[알고리즘] #13. 순열과 조합 :: 개발일기🌷 (tistory.com)

[알고리즘] #13. 순열과 조합

[코딩테스트 대비] 순열(Permutation)과 조합(Combination) 알고리즘 (aerocode.net)

[코딩테스트 대비] 순열(Permutation)과 조합(Combination) 알고리즘

룰루랄라 :: [Java] 순열(Permutation), 조합(Combination) (tistory.com)

[Java] 순열(Permutation), 조합(Combination)