Math | Permutation & Combination

순열 : n개의 집합에서 대상 r을 순서 있게 배열하는 가짓수

 

https://practice.geeksforgeeks.org/problems/permutations-of-a-given-string2041/1/

class Solution
{
	public:
	vector<string> buffer;
	string b;
	
	void loop_permutation(string s, vector<int> &check, int level){
	    if (level == s.length() ){
	    	buffer.push_back(b);
	        return;
	    }
	    
	    for (int i=0;i<s.length();i++) {
	        if ( check[i] == 1 ) continue;
	        else {
	            check[i] = 1;
	            b.push_back(s[i]);
                
                //recursive call
	        	loop_permutation(s, check, level+1);
                
                //back track
	            check[i] = 0;
	            b.pop_back();
	        }
	    }
	}
	
	vector<string> find_permutation(string S)
	{
	    vector<int> check(S.length()+1);
	    loop_permutation(S, check, 0);
	    sort(buffer.begin(), buffer.end());
	    return buffer;
	}
};

문제점 : check와 b라는 별도 공간을 사용

 

https://www.geeksforgeeks.org/write-a-c-program-to-print-all-permutations-of-a-given-string/

 

조합 : n개에서 r개를 순열로 뽑은 다음에, 순서는 상관없으니 r개 뽑은 대상들의 가짓수를 제외함

#include <cstdio>
#include <algorithm>
#include <vector>
#include <iostream>
using namespace std;

int n = 5;
int k = 3;
int a[5] = {1, 2, 3, 4, 5};
vector<int> b;

void print(vector<int> b){
	for(int i = 0; i < b.size(); i++){
		cout << b[i] << " ";
	}
	cout << endl;
}

void combi(int start, vector<int> b){

	if (b.size()==k){
		print(b);
		return;
	}
	
	for ( int i=start+1; i<n;i++){
		cout << " i:" << i <<"\n";
		b.push_back(a[i]);
		combi(i,b);
		b.pop_back();
	}
	
	return;

}

int main() {
	combi(-1, b);
	return 0;
}