문자열로 나타낼 수 있는 순열의 개수(경우의 수)

"duck"이라는 글자로 만들 수 있는 순열의 개수는 어떻게 구할 수 있을까?

수학적으로 생각해본다면 duck으로 만들 수 있는 순열의 개수는 첫 자리에 올 수 있는 글자 4개(d,u,c,k), 두번째 자리에 올 수 있는 글자 3개 ... 이렇식으로 계산하고 어렵지 않게 4*3*2*1이라는 결과를 얻을 수 있다.

일반화해서 표현하자면 길이가 n인 글자에 대해서는 n*(n-1)*(n-2)*...*1 이 된다는 것을 알 수 있다.

 

위와 같은 방식으로 코드를 작성할 수 있다.

- 입력: str에는 순열을 만들고자 하는 문자를 넣고 prefix에는 새로 문자들을 넣어서 단어를 만들것이다.

- 함수 작동 방법

1. 이는 재귀함수로 이루어져있다.

2. 재귀가 불릴때마다 str에 있는 글자 하나를 빼서 prefix에 붙여준다.

3. str은 빈 상태가 되면 prefix를 출력한다.

 

처음에 duck을 넣었다면 d,u,c,k에서 각각 한 글자씩 빼서 prefix로 넣고 permutation을 호출한다.

가장 처음으로 아래 함수들이 호출된다. (이 부분이 위에서 설명한 첫 번째 자리에 들어갈 수 있는 경우의 수가 4인 부분이다. d, u, c, k)

permutation("uck", "d")

permutation("dck", "u")

permutation("duk", "c")

permutation("duc", "k")

두번째 자리에 들어갈 수 있는 글자는 첫번째자리에서 이미 prefix로 간 것을 제외하고 나머지 세 글자중에서 선택하면 된다.

가령 가장 위에 permutation("uck", "d")가 호출되었다면 이 상태에서는 u, c, k중 하나가 오면 된다.

이런 방식으로 재귀를 계속 호출하다보면 4*3*2*1의 모든 경우의 수를 확인할 수 있다.

void permutation(string str, string prefix)
{
    if (str.length() == 0)
        cout << prefix << endl;
    else
    {
        for (int i = 0; i < str.length(); i++)
        {
            string tmp = str.substr(0, i) + str.substr(i + 1);
            permutation(tmp, prefix + str[i]);
        }
    }
}

int main()
{
    permutation("duck", "");
}

출력

duck
dukc
dcuk
dcku
dkuc
dkcu
udck
udkc
ucdk
uckd
ukdc
ukcd
cduk
cdku
cudk
cukd
ckdu
ckud
kduc
kdcu
kudc
kucd
kcdu
kcud

 

참고

코딩인터뷰 완전분석