10 min to read
java-순열-중복순열-조합-중복조합
내가 다시 볼려고 정리하는 순열과 조합
![Featured image](/assets/img/work/안드로이드2.jpg)
다시
최근 풀어본 코딩테스트에서 순열과 조합이 항상 출제되었다.
분명히 풀어본 적 있고 이론을 정리한 적 있는데
항상 컴퓨터앞에서 문제를 풀면 헷갈렸다.
오늘 완전 이 페이지 하나로 순열과 조합을 부수려고 한다.
순열
서로 다른 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번째경우
Comments