[ 순열과 조합 구현 ] 재귀를 통한 구현(4 - 중복순열) (C++)

지난 글에서 중복조합에 대해서 알아보았다. 이번 시간에는 중복 순열에 대해서 알아보도록 하자.

[ 조합 알아보기(Click) ]

[ 순열 알아보기(Click) ]

[ 중복조합 알아보기(Click) ]

중복순열을 알아보기전, 먼저 순열에 대해서 한번 더 복습하고 가도록 하자.

순열이라는 것은 순서가 존재하는 수열이기 때문에, { 1, 2 } 와 { 2, 1 } 이 다른 경우이다 라는 것을 말했었다.

중복순열은 이 내용에서 중복이 허용되었다는 점이 추가된 것이다.

즉, { 1, 2, 3 } 에서 2개를 뽑을 때 일반순열의 경우 { 1, 2 } , {1, 3} , { 2, 1} , {2, 3}, { 3, 1}, {3 , 2} 를 출력할 수 있다.

하지만 중복순열의 경우, 뽑았던 카드를 또 뽑아도 되는 중복이 허용되기 때문에 결과가

{ 1, 1 } , { 1, 2}, {1, 3}, { 2, 1 } , {2, 2 }... 이런식으로 진행될 것이다.

그렇다면 어떻게 구현해야 하는지 소스코드를 보고 구체적으로 알아보도록 하자.

[ 소스코드 ]

#include<iostream>
 
#define endl "\n"
#define MAX 5
using namespace std;
 
int Arr[MAX];
int Select[MAX];
 
void DFS(int Cnt)
{
    if (Cnt == 3)
    {
        cout << " { ";
        for (int i = 0; i < 3; i++)
        {
            cout << Select[i] << " ";
        }
        cout << "} " << endl;
        return;
    }
 
    for (int i = 0; i < MAX; i++)
    {
        Select[Cnt] = Arr[i];
        DFS(Cnt + 1);
    }
}
 
int main(void)
{
    for (int i = 0; i < MAX; i++) Arr[i] = i + 1;
    DFS(0);
}

실행결과가 너무 많아서 짤랐다... ( 5개의 숫자 중 3개를 뽑는 중복순열 코드 )

만약, 조합, 순열, 중복조합에 대해서 완벽하게 이해했다면 중복순열은 거저이다. 코드만 봐도 왜 그런지 딱 알 수 있을만큼

너무나도 구현하기 쉽다.

중복조합과 마찬가지로, Select[] 배열이 이미 뽑았니 안뽑았니를 표시해주는 역할이 아닌, 값을 저장해주는 역할을

하고있다. 이 부분은 지난글 에서 충분히 설명했으니, 위의 코드에 대해서만 설명을 하겠다.

보면, 순열 코드와 마찬가지로 재귀호출을 하는 DFS함수에는 Cnt하나만 존재한다. Idx는 순열에서 필요가 없기 때문이다.

또한, for문 안에서 i 가 0부터 반복된다는 점만 유의한다면 중복순열도 쉽게 구현할 수 있을 것이다.