[알고리즘/개념/C++] 중복순열과 중복조합

순열과 조합 문제를 풀다보면, "중복하여" 뽑는 문제에 대해서 처리를 해줘야 하는 경우가 있다.
사실, 순열과 조합의 코드를 잘 이해한다면, 어렵지 않게 응용할 수 있는 부분이지만, 은근히 헷갈릴 수도 있기 때문에, 한번 정리해보려고 한다.

중복순열 (Permutation with repetition)

중복순열은 n개 중에 중복 상관없이 r개를 뽑아서, 줄 세우는 경우의 수이다. 여기서 "중복 상관없이"라는 문장이 애매할 수 있다. 중복이 상관없다는 이야기는 (1,1),(2,2)와 같이, 똑같은걸 뽑아도 상관없다는 이야기이다.

예를들어,3명 중 중복 상관없이 2명을 뽑아서 줄세우는 모든 경우는 아래와 같다.
(1,1),(1,2),(1,3)
(2,1),(2,2),(2,3)
(3,1),(3,2),(3,3)

경우의 수를 뽑을 때를 생각하면 더 간단해진다. 위의 예시를 그대로 가져와서, 풀어보자.
빈자리 2개가 있다고 생각했을 때, 한 자리를 차지할 수 있는 경우의 수는 3가지이다.
즉, 3x3이 되므로, $3\Pi 2$와 같이 $n\Pi r$은 $n^r$과 같아진다.

$n\Pi r$의 경우의 수는 $n^r$ 과 같다.

모든 경우를 보여주는 코드

순열을 짜는 코드는 아는 상태에서, 조금만 응용해보면 중복순열이 되는데, 어느 부분을 손보면 될까?

#include <bits/stdc++.h>
using namespace std;

int n, r;
void makePermutation(vector<int> v, vector<bool> used, int depth)
{
  if (depth == r)
  {
    for (int i = 0; i < v.size(); i++)
    {
      cout << v[i] + 1 << " ";
    }
    cout << '\n';
    return;
  }
  for (int i = 0; i < n; i++)
  {
    if (used[i] == true)
    {
      continue;
    }
    used[i] = true;
    v[depth] = i;
    makePermutation(v, used, depth + 1);
    used[i] = false;
  }
}

int main()
{
  cin >> n >> r;
  vector<int> v(r);
  vector<bool> used(n);
  makePermutation(v, used, 0);
  return 0;
}

위의 코드에서 어떤 부분을 수정해야, 중복을 얻어낼 수 있을까?? 중복을 체크하는 부분이 어디일까? 바로, used[i] 이 부분에서 우리는 이 숫자를 썻는지, 안썻는지 확인을 한다. 따라서, used이 부분과 관련된 곳을 다 제거해주면 완성될거 같다. 사실 , 이 방법 외에도 좋은 방법이 있을 수 있다.

#include <bits/stdc++.h>
using namespace std;

int n, r;

void makePermutation(vector<int> v, int depth)
{
  if (depth == r)
  {
    for (int i = 0; i < v.size(); i++)
    {
      cout << v[i] + 1 << " ";
    }
    cout << '\n';
    return;
  }
  for (int i = 0; i < n; i++)
  {
    v[depth] = i;
    makePermutation(v, depth + 1);
  }
}

int main()
{
  cin >> n >> r;
  vector<int> v(r);
  makePermutation(v, 0);
  return 0;
}

실행결과

중복조합 (Combination with repetition)

중복조합은 , 중복된걸 뽑아도 상관을 쓰지 않는 경우의 수이다. 예를들어, [1,2,3]이 있다면,
(1,1),(1,2),(1,3)
(2,2),(2,3)
(3,3)
의 경우의 수가 있을 수 있다.

기존의 조합에서 어떻게하면, 중복을 생각해줄 수 있을까? 그 과정을 생각해보자.

#include <bits/stdc++.h>
using namespace std;

int n, r;
void printV(vector<int> v)
{
  for (int i = 0; i < v.size(); i++)
  {
    cout << v[i] + 1 << " ";
  }
  cout << '\n';
}
void makeCombi(vector<int> v, int start)
{
  if (v.size() == r)
  {
    printV(v);
    return;
  }
  for (int i = start + 1; i < n; i++)
  {
    v.push_back(i);
    makeCombi(v, i);
    v.pop_back();
  }
}
int main()
{
  cin >> n >> r;
  vector<int> v;
  makeCombi(v, -1);
  return 0;
}

start +1하는 부분을 없애주면 될거같다. 왜냐하면, 다음걸 뽑는 동작이니까, start를 또 뽑아주면 됨. 이때, -1부터 시작해주는 부분도 +1이 없기 때문에, 0으로 바꿔주면 끗!

#include <bits/stdc++.h>
using namespace std;

int n, r;
void printV(vector<int> v)
{
  for (int i = 0; i < v.size(); i++)
  {
    cout << v[i] + 1 << " ";
  }
  cout << '\n';
}
void make_R_Combi(vector<int> v, int start)
{
  if (v.size() == r)
  {
    printV(v);
    return;
  }
  for (int i = start; i < n; i++)
  {
    v.push_back(i);
    make_R_Combi(v, i);
    v.pop_back();
  }
}
int main()
{
  cin >> n >> r;
  vector<int> v;
  make_R_Combi(v, 0);
  return 0;
}