순열과 조합 코드가 계속 헷갈려서 따로 정리해 놓고 수시로 복습해야겠다.

순열

순열을 구할때 주의할 점은 정렬이 된 상태여야 한다는 것이다.

#define swap(type, a, b) do{ type t = a; a = b; b = t; }while(0)

vector<int> v{ 1, 2, 3, 4 };

void permutation(int n, int r, int depth) {
	if (depth >= r) {
    	// TODO start
		for (int i = 0; i < r; i++) {
			cout << v[i] << " ";
		}
		cout << '\n';
        // TODO end
		return;
	}
	for (int i = depth; i < n; i++) {
		swap(int, v[depth], v[i]);
		permutation(n, r, depth + 1);
		swap(int, v[depth], v[i]);
	}
}

// 사용법
permutation(4, 3, 0); // 4P3

순열은 같은 숫자를 고르더라도 위치에 따라 다르게 판별하기 때문에
위치를 기준으로 스왑을 해준다.

물론 next_permutation() 함수를 지원해주지만 이녀석은 nPn 만 구해준다.
nPr로 구하고 싶다면 따로 r개를 뽑아서 argument로 전달해줘야 한다.

조합

vector<int> st;
void combination(int n, int r, int start_index) {
	if (st.size() == r) {
    	// TODO start
		for (auto it : st) cout << it << " ";
		cout << '\n';
        // TODO end
		return;
	}
	for (int i = start_index; i < n; i++) {
		st.push_back(v[i]);
		combination(n, r, i+1);
		st.pop_back();
	}
}

// 사용법
combination(4, 3, 0); // 4C3

조합은 일단 숫자 하나를 고르면 어느 위치에 오든 상관없이 동일하게 판별하기 때문에 숫자 하나를 꺼내서 다른 자료형에 저장하는 식으로 코드를 만든다.