[경우의 수] 순열, 조합, 중복 순열

이번엔 경우의 수를 구하는 순열, 조합, 중복순열에 대해서 알아보겠습니다. 여러분이 많이 알고 있는 경우의 수구하는 알고리즘인데, 이를 넘어서 해당 성분들까지 구해보는 경우를 구해봅시다!!

순열(Permutation)

---

먼저 순열이 어떤 건지 알아봅시다. 기호로 표현하면 nPr이라고 표현합니다. 해석하자면 n개의 성분에서 r개를 뽑아 나열시킨 경우의 수가 되겠네요.

대표적인 예로 줄 세우기가 될텐데, 순열은 방향성이 있는 경우의 수입니다. 즉 123이랑 321은 다르다는 거죠.

먼저 순열의 경우의 수를 구하는 식을 보면 이러합니다.

한번 구현해보기에 앞서서 순열이 데이터를 선택하는 절차를 보면 이렇게 되겠죠.

그림처럼 선택된 데이터를 제외한 리스트에서 다른 데이터를 가져오는 방식으로 데이터가 선택됩니다.

제가 여기서 겪은 문제점은 어떻게 선택된 놈을 제외시키지 였습니다. 뭐 그냥 노가다로 지울 수도 있었고, 조건문 으로도 지울 수 있었는데, 감이 안오더라구요.. 그래서 이리저리 검색을 하니까 선택된 데이터는 맨 끝으로 보내버리기를 사용 하더라구요.

void Permutation(int n, int r)
{
    if(r == 0){
        perm.push_back(T);
        return;
    }
    for(int i = n-1; i>=0; i--)
    {
        swap(&data[i], &data[n-1]);
        T.push_back(data[n-1]);
        Permutation(n-1, r-1);
        T.pop_back();
        swap(&data[i], &data[n-1]);
    }
}

먼저 i를 0부터 돌려서 마지막에 if(i==n)을 주기보단 그냥 맨 끝부터 돌리면 편하니까 for loop를 저렇게 줬고, i번째 데이터가 선택이 되면 그 데이터는 뒤로 보내고 다시 recursion해주면 선택된 값이 뒤로 사라져서 검색을 안하게 되고... 이해가 되셨나요?? 

그림으로 보면 조금 더 이해가 될 수도 있는데, i가 2일 때 맨 끝번호랑 순서를 바꾸고 다시 함수 call로 들어가서 i가 1번일 때 검색하는 내용입니다. 

그리고 vector T에 해당 성분을 집어넣고 함수 호출이 끝나면 집어 넣었던 성분을 pop하고 다시 원위치로 돌리는데, 

그 이유는 for loop를 돌 때, 해당 loop 다음 loop는 함수 호출이 되었을 때의 성분을 사용해야 하기 때문에 원상태로 돌려놓는 것입니다. 

순열의 경우의 수 공식은 위에 사진으로 보았듯이 n부터 1씩 차감하면서 r개 곱하면 끝!

int PermutationAmount(int n, int r)
{
    int result = 1;
    for(int i=0; i<r; i++)
    {
        result*=(n-i);
    }
    return result;
}

조합(Combination)

---

이번엔 조합입니다! nCr로 표시하죠. 경우의 수는 아래처럼 표현이 가능합니다.

조합은 n개의 데이터에서 r개를 뽑는 경우의 수입니다. 순열과 다른 점은 순열은 데이터를 나열하는 것 이기에 순서가 중요하지만, 조합은 데이터 뽑기만 한다는 것이죠.

구현을 할 때에는 순열과의 차이점을 생각한다면 순열 코드에서 한 가지만 변화시키면 된다는 것을 알 수 있습니다.

순열 코드에서 swap을 사용했던 이유는 순열의 경우 선택 되는 놈을 제외하고 나머지 중에 선택하는 것이지만, 사실 조합은 그걸 따질 필요는 없어요.

그림은 조합이 데이터를 선택하는 방법입니다. 조합의 경우엔 선택된 데이터 이후의 데이터만 생각하면 되죠. 그 외 경우는 다른 곳에서 채워줄 수 있으니까.

결론! 스와핑이 필요없다!

void combination(int n, int r){
    if(r == 0){
        com.push_back(T);
        return;
    }else if(n<r){
        return;
    }
    else {  //loop이 아님
        T.push_back(arr[n-1]);
        combination(n-1, r-1);  
        T.pop_back();
        combination(n-1, r);        
    }
}

지금 재귀가 두 부분에서 일어나는데, 첫 번째는 r-1로 들어가고 두 번째는 r로 들어갑니다. 

이 둘의 차이는?? n-1번째 데이터를 추가 하는지 안하는지 차이입니다. 

조합은 n개 중 r개 선택하는 것이니까, 선택이 되고 다른 성분을 검색하는 게 r-1, 선택 안하고 나머지에서 체크하는게 r이 되겠습니다. 

조합에서는 파스칼의 삼각형이라는 특이한 공식이 있어요. 파스칼의 삼각형 공식은 이러합니다. 

오호 dynamic Programming에서 많이 보였던 점화식 형태네요. 왜 이게 점화식이 될 수 있냐면, 조합의 성질에 의해서 nCr에서 r이 0이거나 n인 경우는 1의 경우의 수가 됩니다. 당연한거죠? n개 중에 n개, 0개 고르는 경우는 1이니까.

int CombinationResult(int n, int r)
{
    if(n==r||r==0) return 1;
    // nCr = (n-1)C(r-1) + (n-1)C(r)
    return CombinationResult(n-1,r-1) + CombinationResult(n-1, r);
}

이렇게 되겠네요 그럼!! 겁나 간단!! 아 물론 위의 기본 nCr공식을 사용해도 됩니다.

중복순열(Redundant Permutation)

---

이번엔 중복 순열입니다!! 사실 이거 공부하려고 했다가 순열, 조합공부함. 중복 순열은 순열인데 같은 데이터가 선택될 수 있기 때문에 중복이 붙었습니다. 그럼 순열코드에서 다른건 뭐가 될까요?? 순열을 구현할 때 선택된 데이터가 선택 되지 말라고 스와핑하고 인덱스에서 검색 못하게 순번을 차감해서 recursion했던 것을 없애면 되겠네요!!

void RP(int n, int r){
    if(r == 0){
        perm.push_back(T);
        return;
    }
    for(int i = n-1; i>=0; i--){
        swap(&data[i], &data[n-1]);
        T.push_back(data[n-1]);
        RP(n, r-1);
        T.pop_back();
        swap(&data[i], &data[n-1]);
    }
}

이해가 되시나요? 다른 것은 선택된 놈도 다시 선택될 수 있다는 것!! 

그럼 swap은 왜 안 빠졌을 까요? 순열은 본래가 순서가 중요하기 때문이에요. 

즉, 같은 1이어도 다른 순서면 다른 값이라는 거죠. 그렇기 때문에 순서을 바꿔주기 위한 swap이 되겠습니다!! 

3 코드 모두 vector T를 만들고 2차원 vector인 perm, com에 저장하는데, 이는 경우를 저장하기 위한 것입니다! 

코드는 아래에 있습니다! 

중복 순열 순열 조합