[Algorithm] 조합 구현

구현1

nCr

#include<iostream>
using namespace std;

void combination(int arr[], int n, int r, int index, int target, int comb[])
{
	cout << "N: " << n << " R: " << r << " index: " << index << " Target: " << target << endl;
	if (r == 0) {
		for (int i = 0; i < index; i++) {
			cout << comb[i];
		}
		cout << endl;
	} else if (target == n) {
		return;
	} else {
		comb[index] = arr[target];
		combination(arr, n, r - 1, index + 1, target + 1, comb);
		combination(arr, n, r, index, target + 1, comb);
	}
}

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

	int* comb = new int[5];
	combination(arr, 5, 3, 0, 0, comb);
}

 

설명

1. comb[index] = arr[target];
2. combination(arr, n, r - 1, index + 1, target + 1, comb);
3. combination(arr, n, r, index, target + 1, comb);

 

1: 해당 인덱스에 타겟을 넣는다

2: 다음값을 넣기위해 반복한다

2.1: 전부다 고르면 1,2,3 이렇게 담긴 배열을 리턴한다.

 

3: 2.1 번에서 1,2,3 이 다 골라 졌고 출력이 된후 리턴이 된다.

3.1:  앞에 target 만 증가 함으로 1,2,3 상태에서 마지막 배열 값에 4를 집어 넣는다.

 

반복하면서 모든 조합을 출력해 나간다.

 

 

구현

모든 조합 출력해보기

 

2진수를 이용하여 모든 조합을 출력해보기

A, B, C 의 모든 조합을 구해보려면

다음과 같이 생각하면된다.

 

2^3 = 8 이므로 8개의 조합이 나온다

0: 000 => 선택안함

1: 001 => C 선택

2: 010 => B 선택

3: 011 => B,C 선택

4: 100 => A 선택

5: 101 => A, ,C 선택 

6: 110 => A, B 선택

7: 111 => ABC 선택

 

구현

코드는 출력이 조금 다르다.

비트연산을 수행하기 때문.

 

1. 1이들어온다 

2. 비트연산을 한다. 

3. 001 >> 0 & 1  즉 비트 쉬프트 를 반복하면서 결과가 1이면 출력.

#include<iostream>
using namespace std;

void allCombination(char arr[], int length)
{

	for (int i = 0; i < (1 << length); i++) {
		for (int j = 0; j < length; j++) {
			if (i >> j & 1) {
				cout << arr[j] << " ";
			}
		}
		cout << endl;
	}

}

int main()
{
	char arr[3] = { 'A', 'B', 'C'};
	int length = 3;

	char* comb = new char[3];
	allCombination(arr, length);
}