[C++] 순열, 조합

표준 라이브러리로는 next_permutaion 과 prev_permutaion 이 있습니다.

next_permutaion : "오름차순의 배열"을 기반
prev_permutaion : "내림차순의 배열"을 기반

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

template <typename t>
void pa(t T) {
  for (auto p : T) cout << p << " ";
  cout << "\n";
}

int main() {
  vector<int> v = {1, 2, 3};
  cout << "next_permutaion" << "\n";
  do {
    pa(v);
  } while (next_permutation(v.begin(), v.end()));

  cout << "prev_permutaion" << "\n";
  v = {3, 2, 1};
  do {
    pa(v);
  } while (prev_permutation(v.begin(), v.end()));

  cout << "순열을 뽑아내는 것은 이터레이터가 담당하므로 순수 함수이다. " << "\n";
  pa(v);
  return 0;
}

 

dfs로 전체 순열 뽑아내려면,

#include <iostream>
using namespace std;

void dfs(int n, vector<int> a, vector<bool> v) {
  if (a.size() == n) {
    for (auto p : a) cout << p << " ";
    cout << "\n";
    return;
  }

  for (int i = 1; i <= n; i++) {
    if (!v[i]) {
      v[i] = true;
      a.push_back(i);
      dfs(n, a, v);
      a.pop_back();
      v[i] = false;
    }
  }
}

int main() {
  int n;
  cin >> n;

  vector<int> a;
  vector<bool> visited(n + 1, false);

  dfs(n, a, visited);

  return 0;
}

 

이미 만들어진 배열에서 조합 찾아내기.

// 서로다른 5개의 구슬이 들어있는 구슬망에서
// 3개의 구슬을 뽑는 조합 구현
// nCr = 5C3

int n = 5;
int r = 3;
int arr[] = {1, 2, 3, 4, 5};

vector<int> v;

void combi(int start, vector<int> v) {
  if (v.size() == r) {
    pa(v);
    return;
  }
  for (int i = start + 1; i < n; i++) {
    v.push_back(arr[i]);
    combi(i, v);
    v.pop_back();
  }
  return;
}

int main() {
  combi(-1, v);
  return 0;
}

 

처음부터 넣어보면서 조합 찾아보기

 

#include <iostream>
#include <vector>
using namespace std;

void dfs(int n, int m, vector<int> a, vector<bool> v) {
  if (a.size() == m) {
    for (auto p : a) cout << p << " ";
    cout << "\n";
    return;
  }

  for (int i = 1; i <= n; i++) {
    if (!v[i]) {
      v[i] = true;
      a.push_back(i);
      dfs(n, m, a, v);
      a.pop_back();
    }
  }
}

int main() {
  int n, m;
  cin >> n >> m;

  vector<int> a;
  vector<bool> v(n + 1, false);

  dfs(n, m, a, v);

  return 0;
}