Combination, Permutation, Powerset in C++

Combination

#include <iostream>

using namespace std;

int arr[] = { 1,2,3,4,5,6 };
int t[6] = { 0, };

void printArray(int * a, int n) {
	printf("{ ");
	for (int i = 0; i < n; i++) {
		printf("%d ", a[i]);
	}
	printf("}\n");
}

// nCr = (n-1)C(r-1) + (n-1)C(r)
void nCr(int n, int r, int q) {
	if (r == 0) {
		printArray(t, q);
	}
	else if (n < r) {
		return;
	}
	else {
		t[r - 1] = arr[n - 1];
		nCr(n - 1, r - 1, q);
		nCr(n - 1, r, q);
	}
}

// nHr = (n)H(r-1) + (n-1)H(r)
void nHr(int n, int r, int q) {
	if (r == 0) {
		printArray(t, q);
	}
//	else if (n < r) {
	else if (n < 1) {
		return;
	}
	else {
		t[r - 1] = arr[n - 1];
		nHr(n, r - 1, q);
		nHr(n - 1, r, q);
	}
}


int main() {
	printf("조합\n");
	nCr(4, 3, 3);

	printf("중복조합\n");
	nHr(4, 3, 3);

	return 0;
}

Permutation

#include <iostream>

using namespace std;

// 순열 : 서로 다른 n개 중에 r개를 뽑아서 순서대로 나열하는 방법의 수
// nPr = n * (n-1)P(r-1)
// 순열의 핵심 개념 ? 앞에서 선택한 것을 제외한 나머지가 다음 선택 대상이 된다. 

int arr[] = { 1,2,3,4 };
int t[4] = { 0, };

// nPn
void perm_loop() {
	for (int i = 1; i < 4; i++) {
		for (int j = 1; j < 4; j++) {
			if (j == i) continue;
			for (int k = 1; k < 4; k++) {
				if (k == j || k == i) continue;

				printf("{ %d %d %d }\n", i, j, k);
			}
		}
	}
}

void Swap(int &n1, int &n2) {
	int tmp = n1;
	n1 = n2;
	n2 = tmp;
}

void printArray(int * a, int n) {
	printf("{ ");
	for (int i = 0; i < n; i++) {
		printf("%d ", a[i]);
	}
	printf("}\n");
}

// nPn
void perm_recursive(int k, int n) {
	if (k == n) {
		printArray(arr, n);
	}
	else {
		for (int i = k; i < n; i++) {
			Swap(arr[i], arr[k]);
			perm_recursive(k + 1, n);
			Swap(arr[i], arr[k]);
		}
	}
}

// nPr = n * (n-1)P(r-1)
void perm_nPr(int n, int r, int q) {
	if (r == 0) {
		printArray(t, q);
	}
	else {
		for (int i = n - 1; i >= 0; i--) {
			Swap(arr[i], arr[n - 1]);
			t[r - 1] = arr[n - 1];			// n
			perm_nPr(n - 1, r - 1, q);		// (n-1)P(r-1)
			Swap(arr[i], arr[n - 1]);
		}
	}
}


// nPIr = n * (n)PI(r-1)
void perm_nPIr(int n, int r, int q) {
	if (r == 0) {
		printArray(t, q);
	}
	else {
		for (int i = n - 1; i >= 0; i--) {
			Swap(arr[i], arr[n - 1]);
			t[r - 1] = arr[n - 1];			// n
			perm_nPIr(n, r - 1, q);		// (n)PI(r-1)
			Swap(arr[i], arr[n - 1]);
		}
	}
}

int main() {
	cout << "순열(반복)" << endl;
	perm_loop();

	cout << "\n순열(재귀)" << endl;
	perm_recursive(0, 3);

	cout << "\n순열(점화식)" << endl;
	perm_nPr(3, 3, 3);


	cout << "\n중복순열(점화식)" << endl;	
	perm_nPIr(3, 3, 3);

	return 0;
}

Powerset

#include <iostream>

using namespace std;

// 부분집합 핵심 : 각 원소가 포함되는 경우와 포함되지 않는 경우의 조합

void printArray(int *a, int n) {
	cout << "{ ";
	for (int i = 0; i < n; i++) {
		if (a[i] == 1) {
			cout << i + 1 << " ";
		}
	}
	cout << "}\n";
}

void powerset_loop() {
	int bit[3] = { 0, };
	for (int i = 0; i <= 1; i++) {
		bit[0] = i;
		for (int j = 0; j <= 1; j++) {
			bit[1] = j;
			for (int k = 0; k <= 1; k++) {
				bit[2] = k;

				printArray(bit, 3);
			}
		}
	}
}

void powerset_sum(int n) {
	for (int i = 0; i < (1 << n); i++) {	// (1 << n) : 2^n
		cout << "{ ";
		for (int j = 0; j < n; j++) {
			if (i &(1 << j)) {				// i &(1 << j) : i의 j번째 bit가 1인지 검사
				cout << j + 1 << " ";
			}
		}
		cout << "}\n";
	}
}

int main() {
	cout << "부분집합(반복)" << endl;
	powerset_loop();

	cout << "부분집합(bit)" << endl;
	powerset_sum(3);


	return 0;
}

Powerset sum

#include <iostream>

using namespace std;

int src[] = { -1,3,-9,6,7,-6,1,5,4,-2 };


void powerset_sum(int n) {
	for (int i = 0; i < (1 << n); i++) {	// (1 << n) : 2^n
		int sum = 0;
		for (int j = 0; j < n; j++) {
			if (i &(1 << j)) {				
				sum += src[j] ;
			}
		}

		if (sum == 0) {
			cout << "{ ";
			for (int j = 0; j < n; j++) {
				if (i &(1 << j)) {				// i &(1 << j) : i의 j번째 bit가 1인지 검사
					cout << src[j] << " ";
				}
			}
			cout << "}\n";
		}
	}
}

int main() {
	powerset_sum(10);
	return 0;
}