[C++] 순열(nPm), 조합(nCm), 중복순열(nPim), 중복조합(nHm)

*모든 예시는 A, B, C, E, D의 다섯 원소 중 3개의 원소를 뽑는 것으로 다루었습니다

 

 

순열(nPm): 순서가 의미 있는 선택  -> "ABC"와 "ACB"를 다르게 취급하겠다는 것

"순서가 의미 있다" ==> 순서가 바뀌면 다른 것, 다른 경우가 된다

(A -> B -> C의 순서로 뽑음, A -> C -> B의 순서로 뽑음)

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

int n, m;
vector<int> nPm;
bool is_in[9];

void backtracking() {
	if (nPm.size() == m) {
		for (int i : nPm) printf("%d ", i);
		printf("\n");
		return;
	}

	for (int i = 1; i <= n; i++) {
		if (is_in[i]) continue;
		is_in[i] = true;
		nPm.push_back(i);
		backtracking();
		nPm.pop_back();
		is_in[i] = false;
	}
}

int main() {
	scanf("%d%d", &n, &m);
	backtracking();
}

 

 

조합(nCm): 순서가 의미 없는 선택 -> "ABC"와 "ACB"는 동일하게 취급하겠다는 것.

"ABC", "ACB", "BAC", "BCA", "CAB", "CBA" 모두 같은 것으로 취급함 (A, B, C를 뽑은 경우 1) 

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

int n, m;
vector<int> nCm;

void backtracking(int here) {
	if (nCm.size() == m) {
		for (int i : nCm) printf("%d ", i);
		printf("\n");
		return;
	}

	for (int i = here; i <= n; i++) {
		nCm.push_back(i);
		backtracking(i + 1);
		nCm.pop_back();
	}
}

int main() {
	scanf("%d%d", &n, &m);
	backtracking(1);
}

 

 

중복순열(nPim): 중복을 허용하며 순서가 의미 있는 선택 -> "AAB", "ABA"는 다른 것으로 취급

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

int n, m;
vector<int> nPim;

void backtracking() {
	if (nPim.size() == m) {
		for (int i : nPim) printf("%d ", i);
		printf("\n");
		return;
	}

	for (int i = 1; i <= n; i++) {
		nPim.push_back(i);
		backtracking();
		nPim.pop_back();
	}
}

int main() {
	scanf("%d%d", &n, &m);
	backtracking();
}

 

중복 조합(nHm): 중복을 허용하며 순서는 의미 없는 선택 -> "AAB", "ABA"는 같은 것

"AAB", "ABA", "BAA" 모두 A를 두 개, B를 하나 선택한 경우 1에 속함

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

int n, m;
vector<int> nHm;

void backtracking(int here) {
	if (nHm.size() == m) {
		for (int i : nHm) printf("%d ", i);
		printf("\n");
		return;
	}

	for (int i = here; i <= n; i++) {
		nHm.push_back(i);
		backtracking(i);
		nHm.pop_back();
	}
}

int main() {
	scanf("%d%d", &n, &m);
	backtracking(1);
}

 

 

---

위의 모든 예시들은 N 개 중에서 M개를 선택하는 것이 가정되어 있지만

위의 코드들을 응용하여 N 개 중에서 (1 ~ M) 개를 선택하는 모든 경우의 수를 구하는 것도 가능하다

예를 들어, 프로그래머스의 "모음사전" 문제의 경우

https://school.programmers.co.kr/learn/courses/30/lessons/84512

프로그래머스

A, E, I, O, U의 문자들을 중복해서 순서가 의미 있게 선택하므로 중복순열이지만

5개에서 특정 M개를 고르는 것이 아닌 1~M개를 고르는 경우의 수 모드를 살펴 보아야 한다

 

위의 문제를 중복순열 코드를 이용해서 푼 코드를 첨부한다

물론 위 문제는 훨씬 간단한 풀이법이 있다...^^*

 

해당 코드는 5(=N)개의 모음 중 1~M개를 고르는 경우의 수를 모두 살펴보아야 하므로

5Pi1 + 5Pi2 + 5Pi3 + 5Pi4 + 5Pi5 = 5^1 + 5^2 + 5^3 + 5^4 + 5^5 = 3,905 의 경우의 수를 계산한다

(가지치기를 하긴 하지만.. 찾고자 하는 단어가 사전 상 맨 마지막이면 의미없는 가지치기이다)

 

원래 nPim 의 계산이 n^m이지만 이 경우는 

 

이므로

칸의 개수나 모음의 개수가 커지면 시간복잡도가 어마어마해질 것이다..

#include <string>
#include <vector>

using namespace std;
char moum[5] = {'A', 'E', 'I', 'O', 'U'};
int idx = 0;
int ans;
bool found = false;

void nPim(string str, string word) {
    if(found) return;
    if(str.length() > 5) return;
    if(str.length() >= 1) idx++;
    if(str == word) {
        ans = idx;
        found = true;
        return;
    }

    for(int i = 0; i<5; i++) {
        string tmp(str);
        tmp += moum[i];
        nPim(tmp, word);
    }
}

int solution(string word) {
    int answer = 0;
    nPim("", word);
    answer = ans;
    return answer;
}

보면 재귀함수의 탈출조건을 ==5 에서 >5로 바꿨다

그리고 >=1 이상일 때 찾고자 하는 조건이 만족되었는지 확인해준다

(원래는 ==m 일 때만 해주었지만 여기서는 ==1~m일때를 다 봐야 하므로) 

 

---

조합(nCm)을 예시로 코드 이해하기

nCm pseudo 코드

기본 순열과 조합의 코드 비교하며 이해하기

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

int N = 3;
int M = 2;
vector<int> nCm;

void backtrackingC(int start) {
	if (nCm.size() == M) {
		for (int i = 0; i < M; i++) {
			printf("%d ", nCm[i]);
		}
		printf("\n");
		return;
	}
	//여기를 start부터 시작하는거는 오름차순이라는 뜻임
	//-> 순열이 아닌 조합일 수밖에 없음
	//순열이라면 135 도 정답이고 531도 정답이므로
	for (int i = start; i <= N; i++) {
		nCm.push_back(i);
		backtrackingC(i + 1);
		nCm.pop_back();
	}

}

bool visit[6];
vector<int> nPm;
void backtrackingP() {

	if (nPm.size() == M) {
		for (int i = 0; i < M; i++) {
			printf("%d ", nPm[i]);
		}
		printf("\n");
		return;
	}

	for (int i = 1; i <= N; i++) {
		if (visit[i]) continue;
		visit[i] = true;
		nPm.push_back(i);
		backtrackingP();
		nPm.pop_back();
		visit[i] = false;
	}
}

int main() {
	backtrackingC(1);
	backtrackingP();
}