언어/Java
[Java] 순열(Permutation), 조합(Combination)
쿠큭다스
2021. 12. 23. 12:24
728x90
순열
순열이란 n개의 값 중에서 r개의 숫자를 순서를 고려해서 뽑는 경우를 말한다.
ex) 1, 2, 3의 3개의 배열 중에서 3개를 뽑는 경우
-> [1, 2, 3]과 [1, 3, 2]는 다른 것으로 처리한다.
Java Code
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
public static void permutation(int arr[], int output[], boolean visited[], int depth, 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<arr.length;i++){
if(!visited[i]){
visited[i]=true;
output[depth]=arr[i];
permutation(arr,output,visited,depth+1,r);
visited[i]=false;
}
}
}
|
함수 설명
int arr[] : 원본 배열
int output[] : 출력하고자 하는 배열
boolean visited[] : 방문여부 체크
int depth : 현재 탐색하고 있는 인덱스
int r : 뽑고자 하는 개수
전체 코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
|
public class Main {
public static void main(String[] args) {
int arr[]={1,2,3};
int output[]=new int[arr.length];
boolean visited[]=new boolean[arr.length];
for(int i=0;i<arr.length;i++){
permutation(arr,output,visited,0,i+1);
}
}
public static void permutation(int arr[], int output[], boolean visited[], int depth, 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<arr.length;i++){
if(!visited[i]){
visited[i]=true;
output[depth]=arr[i];
permutation(arr,output,visited,depth+1,r);
visited[i]=false;
}
}
}
}
|
출력 결과
조합
조합이란 n개의 값 중에서 r개의 숫자를 순서를 고려하지 않고 뽑는 경우를 말한다.
ex) 1, 2, 3의 배열 중에서 3개를 뽑는 경우
-> [1, 2, 3]과 [1, 3, 2]는 같은 것으로 처리한다.
Java Code
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
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;
}
}
}
|
함수 설명
int arr[] : 원본 배열
boolean visited[] : 방문여부 체크
int start : 탐색의 시작 인덱스
int depth : 현재 탐색하고 있는 인덱스
int r : 뽑고자 하는 개수
전체 코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
|
public class Main {
public static void main(String[] args) {
int arr[] = {1, 2, 3, 4};
boolean visited[] = new boolean[arr.length];
for(int i=0;i<arr.length;i++){
combination(arr,visited,0,0,i+1);
}
}
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;
}
}
}
}
|
출력 결과
728x90