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

순열

순열이란 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;             }         }     } }

 

출력 결과