[day6] 순열, 조합

#include<iostream>
#include<algorithm>
#define MAX 51
//세줄짜리는 중괄호 필요
#define MYSWAP (a,b) {int t = a ; a = b ; b = t;}
int N;
int R;
using namespace std;
//tc마다 for가 유동적으로 바뀌어지는 경우 : 재귀 사용
/*
<재귀>
1. 탈출조건
2. 탈출 하지 않을 때 어떤 수식

<중복x순열>
- n-> n-1 , r -> r-1
- 뽑아야하는 대상이 r보다 크다 (n>=r)
- 1씩 줄여줄여나갔을 때, r이 0 되면, 탈출
*/
//char src[MAX] = { 'a', 98, 99 }; //마지막 위치 일단 후보
char src[MAX] = { 0, 'a', 'b', 'c' };
char temp[MAX];//현재 선택 보관
void print() {
	printf("[");
	for (int i = 0; i < R; ++i) {
		printf("%c ", temp[i]);
	}puts("]");
}
#if 0
inline void MY_SWAP(char* a, char* b) { //포인터 개념
	int t = *a;
	*a = *b;
	*b = t;
}
inline void MY_SWAP2(char& a, char& b) {
	int t = a;
	a = b;
	b = t;
}
//nPr
void perm1(int n, int r) {
	//n>=r
	if (r == 0) {
		return;
	}
	//마지막 위치 (n-1) , 2, 1, 0 돈다.
	for (int i = n - 1; i >= 0; --i) {
		//현재 위치 선택 후 줄여나가기
		//swap
		int t = src[n - 1];
		src[n - 1] = src[i];
		src[i] = t;


		temp[r-1] = src[n - 1];
		perm1(n - 1, r - 1);

		//되돌려놓기
		t = src[n - 1];
		src[n - 1] = src[i];
		src[i] = t;
	}
}

void perm2(int n, int r) {
	//n>=r
	if (r == 0) {
		return;
	}
	//마지막 위치 (n-1) , 2, 1, 0 돈다.
	for (int i = n - 1; i >= 0; --i) {
		//현재 위치 선택 후 줄여나가기
		//MYSWAP(src[n-1], src[i]);
		//MY_SWAP(&src[n - 1], &src[i]);
		//MY_SWAP(src[n-1], src[i]; -> 참조자 inline함수
		swap(src[n - 1], src[i]);


		temp[r - 1] = src[n - 1];
		perm2(n - 1, r - 1);

		//되돌려놓기
		//MYSWAP(src[n-1], src[i])
		MY_SWAP(&src[n - 1], &src[i]);
	}
}
#endif
void perm3(int n, int r) {
	if (r == 0) {
		print();
		return;
	}

	for (int i = n; i; --i) {
		swap(src[n], src[i]);

		temp[r - 1] = src[n];
		perm3(n - 1, r - 1);

		swap(src[n], src[i]);
	}
}
/*
	중복 순열: 직전에서 사용한 것, 또 사용 가능!
	n은 줄지 않음!(뽑는 대상 개수는 줄지 않는다.)
*/

void perm_not_dup(int n, int r) {
	if (r == 0) {
		print();
		return;
	}

	for (int i = n; i; --i) {
		swap(src[n], src[i]);

		temp[r - 1] = src[n];
		perm3(n, r - 1); //n-1 이 아닌 n으로 

		swap(src[n], src[i]);
	}
}

void pi(int n, int r) { //이거는 이상ㅎ...
	if (r == 0) {
		print();
		return;
	}

	for (int i = n; i; --i) {
		temp[r] = src[i];
		pi(n, r - 1);
	}
}

/*
	중복 x 조합
	1) 포함되는경우: n-1Cr-1
	2) 포함되지 않는 경우: n-1Cr

	포함되는 경우에서 일을 해야함.
*/

void comb(int n, int r) {

	if (r == 0) { //포함되는 경우 r이 계속 준다.
		print();
		return;
	}

	if (n < r) {
		return;
	}
	temp[r] = src[n];
	comb(n - 1, r - 1); // 포함되는 경우
	comb(n - 1, r); //포함되지 않는경우
}
/*
	중복조합
*/
void H(int n, int r) {

	if (r == 0) { //포함되는 경우 r이 계속 준다.
		print();
		return;
	}

	if (n < r) {
		return;
	}
	temp[r] = src[n];
	H(n, r - 1); // 포함되는 경우, 재사용 가능
	H(n - 1, r); //포함되지 않았으므로, n-1 유지
}
//nC0 = nCn = nP0 = 1
int comb_cal(int n, int r) { //계산값만 
	if (r == 0 || n == r) return 1; 
	//temp[r] = src[n];
	return comb_cal(n - 1, r - 1) + comb_cal (n - 1, r); 
}
//파스칼의 삼각형 - 이차원 배열
int dp[101][101];
int comb_cal_dp(int n, int r) {
	if (r == 0 || n == r) {
		return 1;
	}
	if (dp[n][r] == 0) {
		dp[n][r] = comb_cal_dp(n - 1, r - 1) + comb_cal_dp(n - 1, r);
	}
	else return dp[n][r];
}
//뽑는 개수가 2개이면, 이중 for문으로 다 해결 가능
//0번자리 안비워도 됨
void Ris2(int n, int r) {
	puts("중복순열: ");
	//중복순열
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= n; ++j) {
			printf("[%c %c]\n", src[i], src[j]);
		}
	}
	puts("중복순열: ");
	//중복X 순열
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= n; ++j) {
			if (i != j) {
				printf("[%c %c]\n", src[i], src[j]);
			}
		}
	}
	puts("조합: ");
	//조합
	for (int i = 1; i < n; ++i) {
		for (int j = 1+i; j <= n; ++j) {
			if (i != j) {
				printf("[%c %c]\n", src[i], src[j]);
			}
		}
	}
	puts("중복조합: ");
	//조합
	for (int i = 1; i <= n; ++i) {
		for (int j = i; j <= n; ++j) {
			printf("[%c %c]\n", src[i], src[j]);
		}
	}

}
int main(int argc, char** argv)
{
	N = 3;
	R = 2; 
	perm3(N, R);
	puts("===========");
	perm_not_dup(N, R);
	puts("===========");
	pi(N, R);
	puts("============");
	//부분집합 뽑기
	for (int i = 0; i <= N; ++i) {
		R = i;
		comb(N, R);
	}
	puts("===============");
	N = 100, R = 2;
	cout << comb_cal(N, R) << endl;
	Ris2(3, 2);
	return 0;//정상종료시 반드시 0을 리턴해야합니다.

}


/*
회사 납품 최대-최소 가 최소
비정렬 데이터 들어옴 -> 정렬시키기
해당 구간의 최대, 최소는 포함시키고, 해당 구간 내에서 몇개 순서없이 뽑기(조합)
nC3 + nC4 + ... nCn 구하기

nC0 + nC1 + ... + nCn = 2^n

Todo: 5C3 + 5C4 + 5C5 = 2^n - (nC0 + nC1 + nC2)


key는 lower_bound로 인덱스 찾고
k = start - end - 1 (구간 안 count)
*/

/*
baby-gin Game 
: 10장 중 임의로 6장 뽑았을때
- 연속된 번호 : run
- 똑같은 숫자 3개: triplet

how?
6! - 순열 
*/