순열과 조합의 차이

순열

순서가 있는 조합 (중복 허용X) => 순서가 있으므로, 중복을 허용하지 않습니다.

ex) 

A B C 가 있을 때 이 세명을 세울 수 있는 방법의 개수를 구하시오.

=>  (A B C) (A C B) (B A C) (B C A) (C A B) (C B A)

=> n * (n-1) * (n-2) ....*1

=> nCp

=> 3* 2* 1

 

int main()
{   
    string example ="1234";
    do{
        cout <<example <<'\n';
    }while(next_permutation(example.begin(), example.end()));
    return 0;
}

<순열 예시 CODE>

순열 예시 출력

 

조합

 

순서가 없는 조합(중복 비허용) => 순서가 없으므로 중복을 허용하지 않습니다.

=> 사전 정의 : 조합(Combination)이란 n개의 원소를 갖는 집합에서 m(n 이하의 자연수) 개를 선택하여 만드는 부분집합

=> 재귀적 방법과 next_permutation을 통해 구현할 수 있습니다.

 

int main()
{
    string s = "1234";
    int len = s.size();

    for (int i = 1; i <= len; i++) {
        vector<bool> v(len - i, false);
        v.insert(v.end(), i, true);
        cout << "=============== " << i << "개 ===============\n";
        do {
            string temp = "";
            for (int k = 0; k < len; k++) {
                if (v[k]) temp += s[k];
            }
            cout << temp << "\n";
        } while (next_permutation(v.begin(), v.end()));
        cout << "===================================\n";
    }

    return 0;
}

<조합 예시 CODE>

1개를 뽑을 때, 2개를 뽑을 때..4개를 뽑을 때를 구현하여 실행한 화면

 

---

참고 블로그 : https://notepad96.tistory.com/entry/C-조합 Combination-구하기

C++ 조합(Combination) - next_permutation

 

https://codingham.tistory.com/181

백준 1015 - 수열 정렬

 

=> 백준에는 간단한 수열 문제가 있습니다. 보시는 블로그에서 수열 혹은 순열을 검색하여 해당 문제들 풀이를 확인할 수 있습니다.