순열, 조합, 부분집합

순열, 조합, 부분집합

순열, 조합, 부분집합을 만드는 알고리즘 정리

---

 

 

 

 

 

순열

순열이란?

서로 다른 n 개 중 r 개를 골라 순서를 고려해 나열한 경우의 수.

1, 2, 3, 4 중 3개를 뽑아 순열을 만든다면 가능한 경우는 다음과 같다.

{1, 2, 3}, {1, 2, 4}, {1, 3, 2}, {1, 3, 4}, {1, 4, 2}, {1, 4, 3}, {2, 1, 3}, ... , {4, 2, 3}, {4, 3, 1}, {4, 3, 2}

 

순서를 고려해야 하므로 반복문을 이용하여 가장 앞의 원소부터 확인해야 한다.

또한, 중복은 허용하지 않기 때문에 포함 여부를 확인해야 한다.

void Permutation(vector<int>& nums, vector<bool>& checked, vector<int>& perm)
{
  if(perm.size() == n/*순열의 길이*/)
  {
    // 순열 처리
    
    return;
  }
    
  for(int i = 0; i < nums.size(); i++)
  {
    // 포함되지 않은 수만 처리
    if(!checked[i])
    {
      // nums[i]를 포함
      checked[i] = true;
      perm.push_back(nums[i]);
      Permutation(nums, checked);
      
      // nums[i]를 미포함
      checked[i] = false;
      perm.pop_back(nums[i]);
    }
  }
}

 

C++ STL에서도 next_permutation, prev_permutation이란 순열을 생성하는 함수들을 제공한다.

이 함수들은 <algorithm> 헤더에 포함되어 있다.

사용법은 다음과 같다.

void Permutation(vector<int>& nums)
{
  //정렬
  sort(nums.begin(), nums.end());
  
  do
  {
    //순열 처리
    for(auto n : nums)
    {
      cout << n << " ";
    }
    cout << "\n";
  }while(next_permutation(nums.begin(), nums.end()));
}

주의할 점이 하나 있다.

next_permutation은 양방향 iterator를 매개변수로 받아 요소들을 비교하여 순열을 생성한다.

이때, 컨테이너(vector)가 오름차순으로 정렬되어 있지 않으면 올바른 결과가 나오지 않는다.

반대로 prev_permutation은 내림차순으로 정렬되어 있어야 한다.

 

또한, STL의 *_permutation은 원하는 개수의 순열을 생성하지 못한다.

컨테이너 전체 길이의 순열만 생성가능하다.

---

 

 

 

 

 

조합

조합이란?

서로 다른 n개 중에서 r개(n≥r) 취하여 조를 만들 때, 이 하나하나의 조를 n개 중에서 r개 취한 조합이라고 한다.

1, 2, 3, 4중 3개를 뽑아 조합을 만든다면 가능한 경우의 수는 다음과 같다.

{1, 2, 3}, {1, 2, 4}, {1, 3, 4}, {2, 3, 4}

 

순열과 다른 점은 순서와 무관하다는 점이다.

즉, {1, 2, 3} 과 {1, 3, 2}는 같은 것으로 취급한다.

또한, 중복을 허용하지 않지만 포함 여부는 확인하지 않아도 된다. 

현재까지 처리한 index부터 조합에 포함시키면 되기 때문이다.

void Combination(vector<int>& num, vector<int>& comb, int idx)
{
  if(comb.size() == n/*조합의 길이*/)
  {
    // 조합 처리
    
    return;
  }
  
  for(int i = idx; i < num.size(); i++)
  {
    comb.push_back(num[i]);
    Combination(num, comb, idx+1);
    
    comb.pop_back();
  }
}

 

순열을 이용하여 조합을 구할 수도 있다. 

0과 1로 구성된 순열을 생성하여 1에 해당하는 원소만 조합에 포함시키면 된다. 

void Combination(vector<int>& nums)
{
  // {0, 0, 1, 1...}과 같은 형태로 세팅(1: 포함, 0: 미포함)
  vector<int> indicator(nums.size(), 1);
  for(int i = 0; i < indicator.size()-n; i++)
  {
    indicator[i] = 0;
  }
   
   do
   {
     // 조합 처리
     if(indicator[i] == 1)
     {
       // 1인것만 처리
     }
   }while(next_permutation(indicator.begin(), indicator.end());
}

---

 

 

 

 

 

부분집합

부분집이란?

두 집합 a, b에서 x∈a인 임의의 원소 x에 대하여 반드시 x∈b일 때, a를 b의 부분집합이라 한다.

1, 2, 3, 4로 부분집합을 만들면 다음과 같다.

{∅}, {1}, {2}, {3}, {4}, {1, 2}, ... {1, 2, 3, 4}

 

부분집합을 만드는 개념은 단순하다.

어떠한 원소를 포함 시켰을 때와 그러지 않았을 때를 모두 확인하면 된다.

void Subset(vector<int>& nums, vector<int>& subset, int depth)
{
  if(depth == nums.size())
  {
    // 부분집합 처리
    
    return;
  }
  
  subset.push_back(nums[depth]);
  Subset(nums, subset, depth+1);
  
  subset.pop_back();
  Subset(nums, subset, depth+1);
}

 

STL에서 제공하는 bitset을 이용하여 부분집합을 생성할 수 있다.

1을 비트로 표현하면 001, 2를 비트로 표현하면 010 이기 때문에 이를 이용하여 비트가 1인 부분에 해당하는 원소를 포함하는 집합을 모으면 부분집합이 된다.

void Subset(vector<int>& nums)
{
  for(int i = 0; i < (1 << nums.size()); i++)
  {
    for (int j = 0; j < nums.size(); j++) 
    {
      if (i & (1 << j))
      {
        // 부분집합 처리
        // nums[j]를 포함시킴
      }
    }
  }
}

---