[알고리즘/Algorithm]순열(Permutation)/조합(Combination)/부분집합(Power Set)

순열(Permutation) 

서로 다른 것들 중 몇 개를 뽑아서 한줄로 나열하는 것 (nPr = n!)

n>12인 경우, 시간 복잡도 폭발적으로 상승

void permutation(int cnt) {
    if (cnt == r) {
        // 순열 생성 완료
        return;
    }

    for (i 1 to n) {
        if (isSelected[i]) continue;
        numbers[cnt] += i;
        isSelected[i] = true;
        permutation(cnt + 1);
        isSelected[i] = false;
    }
}

 

조합(Combination)

서로 다른 n개의 원소 중 r개를 순서 없이 골라낸 것

void combination(int cnt int index) {
    if(cnt == r) {
        // 조합 생성 완료
        return;
    }

    for (i index to n-1) {
        numbers[cnt] = i;
        combination(cnt+1, index+1);
    }
}

파스칼의 삼각형 공식을 사용하면 코드가 더욱 간단하다. nCr = n-1Cr-1 + n-1Cr

int combination(int n, int r) {
    if (n == r || r == 0) return 1; 
    return combination(n-1, r-1) + combination(n-1, r);
}

 

 

부분집합(Power Set)

집합에 포함된 원소들을 선택하는 것

공집합 포함한 부분집합의 수는 2^n개

void subSet(int cnt) {
    if (cnt == N) {
        // 부분집합 완성
        return;
    }

    isSelected[cnt] = true;
    subSet(cnt+1);
    isSelected[cnt] = false;
    subSet(cnt+1);
}