순열&조합

개념

조합(Combination) : 순서 바뀜 허용 안함, 중복 허용 안함, nCr = n! / r! * (n-r)!

순열(Permutation) : 순서 바뀜 허용,         중복 허용 안함, nPr = nCr x r!

*순서 바뀜

ex) 1 1 2 & 1 2 1 --> Per 허용, Com 허용X

 

ex) {1,2,3} 

조합(3C2): {1,2}, {2,3}, {3,1}

순열(3PC) : {1,2}, {2,1}, {2,3}, {3,2}, {3,1}, {1,3}

 

조합(3C2) : {1,2,3}

순열(3PC) : 3개의 우너소로 조합 가능한 모든 구성 : 3P3 (nPn = n!) 

{1,2,3}, {1,3,2}, {2,1,3}, {2,3,1}, {3,1,2}, {3,2,1} 

 

순열(Permutation)는 w=0

조합(Combination)은 w=num

단, 중복을 허용할 시 visit배열을 없애 준다.!!

 

코드

void Permutition(int ctttt, int num )
{
	if(ctttt==3)
	{
		vector <int > ans;		
		for(int i = 0 ; i < vvvvv_.size() ; i++)
		{
			cout <<" " <<vvvvv_[i]   ; 
		}
		cout<< endl;
		return ;
	}

//permu는 w=0 
	for(int w= 0 ; w<5 ;w ++)
	{
		if(!vii[w])
		{	vii[w]=true;
		vvvvv_.push_back(ex_Num[w]); //0	
		Permutition(ctttt+1,w);
		vvvvv_.pop_back(); 
		vii[w] =false;
		} 
	}

}
void Combination(int ctttt, int num )
{
	if(ctttt==3)
	{
		vector <int > ans;		
		for(int i = 0 ; i < vvvvv_.size() ; i++)
		{
			cout <<" " <<vvvvv_[i]   ; 
		}
		cout<< endl;
		return ;
	}

//combi는 w=num
	for(int w= num ; w<5 ;w ++)
	{
		if(!vii[w])
		{	vii[w]=true;
		vvvvv_.push_back(ex_Num[w]); //0	
		Combination(ctttt+1,w);
		vvvvv_.pop_back(); 
		vii[w] =false;
		} 
	}

}