모든 조합을 구하는 문제 (순열)

나온 문제는 숫자가 지정되면 가능한 모든 순열을 구하고, 소수의 개수를 구하라는 문제였다.

 

처음에는 직접 경우의 수를 다 구할려고 했는데, 코드도 엄청 길어지고, 복잡하더라.

 

거의 대부분의 수학적인 문제는 이미 라이브러리에 구현되있으니 찾으면 나올꺼라 생각했고, 역시나 나왔다.

 

permutation 함수 자체가 이미 있었다.

 

그래서 나온 방법들은 대부분 비슷했다.

 

do-while 문을 이용하여 다음 수열을 계속해서 만드는 것.

 

그런데 그냥 do-while문만 하면 총 길이와 같은 경우의 수만 나온다.

 

{1, 2, 3, 4} 가 있으면

1234 1243 1324 1342 1423 1432 2134 2143 2314 2341 2413 2431 3124 3142 3214 3241 3412 3421 4123 4132 4213 4231 4312 4321 

만 나오는 것이다.

 

그래서 각 크기별로 만들기 위해서 외부에서 for문을 하나 더 돌렸다.

 

for(int i=0; i<number.size(); i++)

{

    do

    {

        for(int j=0; j<i+1; j++)

        {

            printf("%c ", number[j]);

        }

    }

    while(next_permutation(number.begin(), number.end()));

}

 

소수 구하는 것은 에라토네스의 체를 이용하여 함수를 만들었다.