#알고리즘_조합과 순열(조합, 중복조합, 순열, 중복순열) - Java

1. 조합(Combination)

서로 다른 n개에서 r개를 뽑는 경우 => (n)C(r) => n! / (n-r)! * r!

 

2. 중복 조합(Combination with repetition)

서로 다른 n개에서 r개를 뽑는 데, r개의 요소가 중복되어도 상관 없음 nHr => (n+r-1)C(r) (n-r+1)! /  ( (n-r)! * r!))

 

3. 순열(Permutation)

서로 다른 n개의 원소에서 r개를 중복없이 골라 순서에 상관있게 나열 => nPr => n!/(n-r)!

 

4. 중복 순열(Permutation with repetition)

서로 다른 n개의 원소에서 r개를 중복으로 골라 순서에 상관있게 나열 => n^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 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113

import java.util.ArrayList;   public class combination {     static int arr[] =  { 1, 3, 5, 7, 9 };     static boolean visit[] = new boolean[arr.length];     static int cnt=0;     static ArrayList<Integer> arrList = new ArrayList<>();     public static void main(String[] args) {         combination(arrList, arr.length, 3, 0);         System.out.println("Count = "+cnt);         System.out.println();         cnt=0;                  arrList = new ArrayList<>();         combination_repetition(arrList, arr.length, 3, 0);         System.out.println("Count = "+cnt);         System.out.println();         cnt=0;                  arrList = new ArrayList<>();         permutation(arrList, visit, arr.length, 3);         System.out.println("Count = "+cnt);         System.out.println();         cnt=0;                  arrList = new ArrayList<>();         permutation_repetition(arrList, arr.length, 3);         System.out.println("Count = "+cnt);     }          // 조합 = 서로 다른 n개에서 r개를 뽑는 경우 => (n)C(r) => n! / (n-r)! * r!     public static void combination(ArrayList<Integer> arrList, int n, int r, int index) {         if(r==0) {                          for(int i=0; i<arrList.size(); i++) {                 System.out.print(arrList.get(i)+" ");             }System.out.println();             cnt++;             return;         }                  if(index == n)             return;                  arrList.add(arr[index]);         combination(arrList, n, r-1, index+1); //뽑았음-> r-1         arrList.remove(arrList.size()-1);    //위에서 뽑은거 롤백         combination(arrList, n, r, index+1); //안뽑았으니 r              }     // 중복 조합 = 서로 다른 n개에서 r개를 뽑는 데, r개의 요소가 중복되어도 상관 없음 nHr => (n-r+1)C(r) (n-r+1)! /  ( (n-r)! * r!))     public static void combination_repetition(ArrayList<Integer> arrList, int n, int r, int index) {         if(r==0) {             for(int i=0; i<arrList.size(); i++) {                 System.out.print(arrList.get(i)+" ");             }System.out.println();             cnt++;             return;         }                  if(index == n)             return;                  arrList.add(arr[index]);         combination_repetition(arrList, n, r-1, index); //뽑았음-> r-1 중복을 허용하니까 index는 고정         arrList.remove(arrList.size()-1);    //위에서 뽑은거 롤백         combination_repetition(arrList, n, r, index+1); //안뽑았으니 r, index+1              }          // 순열 = 서로 다른 n개의 원소에서 r개를 중복없이 골라 순서에 상관있게 나열 => nPr => n!/(n-r)!     public static void permutation(ArrayList<Integer> arrList, boolean[] visit, int n, int r) {         if(arrList.size() == r) {             for(int i : arrList) {                 System.out.print(i+" ");             }System.out.println();             cnt++;             return;         }else {             for(int i=0; i<n; i++) {                 if(!visit[i]) {                     visit[i] = true;                     arrList.add(arr[i]);                     permutation(arrList, visit, n, r);                     arrList.remove(arrList.size()-1);                     visit[i] = false;                 }             }         }     }     // 중복 순열 = 서로 다른 n개의 원소에서 r개를 중복으로 골라 순서에 상관있게 나열 => n^r     public static void permutation_repetition(ArrayList<Integer> arrList, int n, int r) {         if(arrList.size() == r) {             for(int i : arrList) {                 System.out.print(i+" ");             }System.out.println();             cnt++;             return;         }else {             for(int i=0; i<n; i++) {                                  arrList.add(arr[i]);                 permutation_repetition(arrList, n, r);                 arrList.remove(arrList.size()-1);                          }         }     }          }   Colored by Color Scripter

cs