순열 구하기 - next_permutation, 재귀

반복문으로 next_permutation 메서드를 이용해서 가능한 순열의 갯수를 구할 수 있다

next_permutation메서드 안에 시작점, 끝점을 넣어주고 do - while 문으로 돌면 해당 배열 안의 원소들이 

가능한 경우의 수 만큼 배치된다

 

! 그냥 while 문의 경우 마지막 순열을 계산한 후 더 이상 계산할 순열이 없으므로 순열내 원소를 출력하지 않고

반복문이 종료되버린다 , do-while 문을 사용

 

! 오름차순을 기준으로 순열을 만들기때문에 정렬된 상태로 메서드를 호출해야한다

int main() {
    int a[] = {1,2,3};
    do{
        for (int i : a) {
            cout << i << " ";
        }
        cout << '\n';
    }while(next_permutation(&a[0], &a[0] + sizeof(a)/sizeof(int)));
    return 0;
}

 

-- 재귀를 이용한 방식

using namespace std;
int a[3] = {1, 2, 3};
int n = 3, r = 3;
void print()
{
    for (int i = 0; i < r; i++)
    {
        cout << a[i] << " ";
    }
    cout << "\n";
}
void makePermutation(int n, int r, int depth)
{
    if (r == depth)
    {
        print();
        return;
    }
    for (int i = depth; i < n; i++)
    {
        swap(a[i], a[depth]);
        makePermutation(n, r, depth + 1);
        swap(a[i], a[depth]);
    }
    return;
}
int main()
{
    makePermutation(n, r, 0);
    return 0;
}