[Math] 순열, 조합, 부분집합 비교

. 순열

서로 다른 n개의 원소 중에서 "중복을 허락하지 않고", "순서를 생각"하며 r개를 일렬로 나열하는 수열

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

// 지정된 자리에 순열 뽑기 // cnt : 현재까지 뽑은 순열의 수 private static void permusation(int cnt) {     // R개를 모두 골랐다면     if(cnt == R) {         System.out.println(Arrays.toString(numbers));         return;     }          for (int i = 0; i < N; i++) {         // 중복 확인         if (isSelected[i]) continue;           numbers[cnt] = input[i]; // 해당숫자 사용해보기         isSelected[i] = true;    // 해당숫자 사용 처리                  permusation(cnt + 1);    // 다음 자리 순열 뽑기                  isSelected[i] = false; // 해당숫자 사용하지 않기     } } Colored by Color Scripter

cs

---

. 중복 순열

서로 다른 n개의 원소 중에서 "중복을 허락"하며 "순서를 생각"하여 r개를 일렬로 나열하는 수열

private static void permusation2(int cnt) {
 
    if(cnt == R) {
        System.out.println(Arrays.toString(numbers));
        return;
    }
 
    for (int i = 0; i < N; i++) {
        numbers[cnt] = input[i]; // 해당숫자 사용
        permusation(cnt + 1);    // 다음 자리 순열 뽑기
    }
}

---

. 조합

서로 다른 n개의 원소 중에서 "중복을 허락하지 않으며" "순서를 생각하지 않고" r개를 택할 때

nCr = n! /

r! * (n-r)!

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

/**  * 지정된 자리에 조합수 뽑기  *   * @param cnt   현재까지 뽑은 조합수의 개수  * @param start 조합에 시작점으로 시도할 인덱스  */ private static void combination(int cnt, int start) {          if (cnt == R) {         System.out.println(Arrays.toString(numbers));         return;     }       // 현자리에 시작위치 수부터 끝위치 수까지 시도     for (int i = start; i < N; i++) {         numbers[cnt] = input[i];         combination(cnt + 1, i + 1);     } } Colored by Color Scripter

cs

---

. 중복 조합

서로 다른 n개의 원소 중에서 "중복을 허락"하여 "순서를 생각하지 않고" r개를 택할 때

private static void combination2(int cnt, int start) {
  
     if (cnt == R) {
         System.out.println(Arrays.toString(numbers));
         return;
     }
     // 현자리에 시작위치 수부터 끝위치 수까지 시도
     for (int i = start; i < N; i++) {
         numbers[cnt] = input[i];
         combination(cnt + 1, i);
     }
}

---

. 부분집합

집합의 원소가 N개일 때, 공집합을 포함한 부분집합의 수는 2^N개

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

public static void generateSubset(int cnt) {     if(cnt == N) {         for (int i = 0; i < N; i++) {             System.out.print(isSelected[i] ? input[i] : "X");             System.out.print("\t");         }         System.out.println();         return;     }       // 부분집합 구성에 포함     isSelected[cnt] = true;     generateSubset(cnt + 1);    // 다음 원소로 넘어감     // 부분집합 구성에 미포함     isSelected[cnt] = false;     generateSubset(cnt + 1);    // 다음 원소로 넘어감 } Colored by Color Scripter

cs

* 참고

출처 : http://blog.naver.com/ao9364/220516757923