10 min to read

java-순열-중복순열-조합-중복조합

내가 다시 볼려고 정리하는 순열과 조합

Featured image

다시

최근 풀어본 코딩테스트에서 순열과 조합이 항상 출제되었다.

분명히 풀어본 적 있고 이론을 정리한 적 있는데

항상 컴퓨터앞에서 문제를 풀면 헷갈렸다.

오늘 완전 이 페이지 하나로 순열과 조합을 부수려고 한다.

순열

서로 다른 N개를 중복 허락하지 않고 R개를 일렬로 나열한다.

중복을 허락하지 않는게 그냥 순열이닌깐

체크 1. 중복을 허락하는건 중복 순열이구나

체크 2. 일렬로 나열한다 = 순서가있다.

순열의 예

일찐이 이찐이 삼찐이 사찐이 4명중 1등 2등을 뽑는다.

1등 한명 2등 한명 뽑기 때문에 중복이 되지 않는다.

그럼 4P2 = 4X3 총 12가지의 방법이 나온다.

그럼 이번엔 1등 2등 3등까지 뽑는다면

4X3X2 24가지의 방법이 나온다.

코드로 구현 참고 블로그 https://bcp0109.tistory.com/entry/%EC%88%9C%EC%97%B4-Permutation-Java?category=848939

코드로 구현

중복이 불가능 하기때문에 중복 체크를 위한 visited[] 배열을 만들어주자.

n개중 r개를 뽑을때

4개중 3개를 뽑을때 예시

arr 배열에는 전체 N의 종류를 넣고

output 배열에는 출력할 값들을 넣고

visited 배열에는

1등을 뽑았으면 걔는 2등 3등 하면 안되닌깐 그거 체크해주는 배열

n에는 전체 arr길이를 넣으면 되고

r에는 내가 뽑을 갯수를 넣으면 된다.

4개중 3개를 뽑는 경우를 보자

일찐이 이찐이 삼찐이 사찐이들이 1등 2등 3등 할 수있는 총 경우

public class 순열 {

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

출력
1 2 3
1 2 4
1 3 2
1 3 4
1 4 2
1 4 3
2 1 3
2 1 4
2 3 1 . . .

중복순열

서로다른 N개를 중복을 허락하고 R개를 뽑는다.

일찐이 이찐이 삼찐이 사찐이중 1등 2등 3등을 뽑는데

1등했던애가 2등도하고 3등도 가능하다고 생각하면

그냥 4X4X4 = 16*4 = 64개의 경우가 나온다.

위의 순열코드에서 중복을 허락하기때문에

visited로 중복을 체크하는 부분만 주석처리하면

1,2,3,4 로 3개를 뽑을때 결과가

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

출력 결과

1 1 1 -1번째경우
1 1 2 -2번째경우
1 1 3 -3번째경우
1 1 4 -4번째경우
1 2 1 -5번째경우
1 2 2 -6번째경우
1 2 3 -7번째경우
1 2 4 -8번째경우
. . . 4 3 4 -60번째경우
4 4 1 -61번째경우
4 4 2 -62번째경우
4 4 3 -63번째경우
4 4 4 -64번째경우

이렇게 결과가 나오게 된다.

조합

조합은 서로 다른 N개를 순서와 상관없이 R개 뽑는것이다.

이전에 1등과 2등을 뽑았다면 지금은 공동 수상 개념이다.

일찐이 이찐이 삼찐이 사찐이가 있는데

2명에게 상을 준다고 하면

1찐이 2찐이가 상을 받는 경우는 2찐이 1찐이가 받는 경우와 같다.

그렇기 때문에

기존에 순열에서 4x3 = 12개였던 순열갯수에서

4x3/2 가되어 = 총 6개의 방법이 나오게 되는것이다.

(1,2),(1,3),(1,4),(2,3)(2,4),(3,4) 이렇게 모든 경우가 된다.

1,2,3,4 중 공동수상 2명을 구해보자

public class 조합 {
	
static int num;
	public static void main(String[] args) {
		
		int arr[] = {1,2,3,4};
		int output[] = new int [arr.length];
		boolean visited[] = new boolean [arr.length];
		int n = arr.length;
		num =0;
		comb(arr, output, visited, 0, n, 2);
		
	}
	
	static void comb(int[] arr, int[] output, boolean[] visited, int start, int n, int r) {
	    if (r == 0) {
	    	for(int i =0 ; i < visited.length; i++) {
	    		if(visited[i]) {
	    			System.out.print(arr[i]+" ");
	    		}
	    	}
	    	num++;
	    	System.out.println("-"+num+"번째경우");
	        return;
	    }
	    for (int i=start; i<n; i++) {
	        if (visited[i] != true) {
	            visited[i] = true;
//	            output[start] = arr[i];
	            comb(arr, output, visited, i + 1, n, r-1);       
	            visited[i] = false;;
	        }
	    }
	}
}

밑에 for문을 보면

for (int i=start; i<n; i++) {
	        if (visited[i] != true) {
	            visited[i] = true;
	            comb(arr, output, visited, i + 1, n, r-1);       
	            visited[i] = false;;
	        }
	    }

i의 시작이 start이다. 그리고 다음 comb를 호출할때 i+1을 해준다.

이렇게하면

(1,2) 를 뽑고나서 뒤에 (2,1)처럼 순서가 역순이 출력되는 경우는 없다.

출력 값
1 2 -1번째경우
1 3 -2번째경우
1 4 -3번째경우
2 3 -4번째경우
2 4 -5번째경우
3 4 -6번째경우

중복조합

N개를 R개만큼 뽑는데 순서와 상관없이 중복해서 뽑아도 된다.

일찐이 이찐이 삼찐이 사찐이 중에 2명을 공동수상하는데

내가 상을 싹슬이 가능하다는 뜻이다.

1.(1찐이,1찐이) 수상을 허용한다.

2.(2찐이,2찐이) 수상을 허용한다.

3.(1찐이,2찐이) 가 수상했다면

4.(2찐이,1찐이) 는 수상할 수 없다.

4명중 2명의 중복조합 구하기

public class 중복조합 {
	
static int num;
	public static void main(String[] args) {
		
		int arr[] = {1,2,3,4};
		int output[] = new int [arr.length];
		boolean visited[] = new boolean [arr.length];
		int n = 4;
		num =0;
		perm(arr, output, visited, 1, n, 2,0);
		
	}
	
	static void perm(int[] arr, int[] output, boolean[] visited, int start, int n, int r,int cnt) {
	    if (cnt == r) {
	    	for(int i =0 ; i < cnt; i++) {
	    		//if(visited[i]) {
	    			System.out.print(output[i]+" ");
	    	//	}
	    	}
	    	num++;
	    	System.out.println("-"+num+"번째경우");
	        return;
	    }
	    for (int i=start-1; i<n; i++) {
	     //   if (visited[i] != true) {
	            visited[i] = true;
	            output[cnt] = arr[i];
	            perm(arr, output, visited, i + 1, n, r,cnt+1);       
	            visited[i] = false;;
	      //  }
	    }
	}
}

출력값

1 1 -1번째경우 1 2 -2번째경우 1 3 -3번째경우 1 4 -4번째경우 2 2 -5번째경우 2 3 -6번째경우 2 4 -7번째경우 3 3 -8번째경우 3 4 -9번째경우 4 4 -10번째경우