순열과 조합, 비트마스크

순열

permutation 함수를 통해 벡터를 순열 순으로 정렬할 수 있다.
이때, a는 정렬되어 있어야 한다.

using namespace std;

int main() {
    vector<int> a = {1, 2, 3};
    sort(a.begin(), a.end());

    do {
        // 이제 a는 while을 돌면서
        // {1, 2, 3}, {1, 3, 2}...로 정렬됨
        for (int x : a) cout << x << " ";
        cout << "\n";
    } while (next_permutation(a.begin(), a.end()));
}

 

조합

5개 중 3개를 선택한다고 하자.
선택한 원소를 1, 아닌 원소를 0으로 00111과 같이 표현할 수 있다.
00111에 대해 permutation을 통해 순열을 구하면 포함 정보를 구할 수 있다.
(00111, 01011, 01101, 01110...)

using namespace std;

int main()
{
    vector<int> idx(n, 0);
    fill(idx.end()-k, idx.end(), 1); // 1이 선택

    do {
        if (idx[i] == 1) // i가 선택된 원소
        {
            ...
        }
    } while (next_permutation(idx.begin(), idx.end()));
}

 

비트마스크

3자리 vector에 대해, 3자리 이진수를 생각해보면
000, 001, 010, 100, 101, 110, 111으로 0을 넣음, 1을 안넣음으로 생각할 수 있다.
원소의 포함/미포함 조합에 대해 특정 로직을 적용하거나, 팀을 나누는 등의 경우에 사용할 수 있다.
이 이진수는 Bitmask를 통해 구한다.

using namespace std;

int main()
{
    vector<int> a = {1, 2, 3};

    for (int mask = 0; mask < (1 << a.size()); i++) // 0(000), 1(001), 2(010)...
    {
        for (int i = 0; i < a.size(); i++)
        {
            if (mask & (1 << i)) // i가 1이면
            {
                a[i] // 포함된 a의 원소
                ...
            }
        }
    }
}