真開心再用vector寫出了這題,嘗試用vector的push_back()及erase()產生所有的組合。在取出元素時檢查未被取出的元素是否有小於該元素的元素(小的元素應該先被取出)。
這題是給一些元素,再給其中部分元素的大小關係,依字典順序輸出在給定的大小關係下所有可能的元素組合。
CODE
#include <iostream> #include <vector> #include <algorithm> using namespace std; #define MAX_LET 26 vector<char> vars; //variables bool consts[MAX_LET][MAX_LET]; //constraints void sort_vars(int left, int right); void comb(vector<char> current, vector<char> pool); int main(){ int i, j; char c, d1, d2; bool flag = false; for(i=0; i<MAX_LET; i++) for(j=0; j<MAX_LET; j++) consts[i][j] = false; while( (c = getchar()) != EOF ){ if( c >= 'a' && c <= 'z' ){ vars.push_back(c); }//get variables else if( c == '\n' ){ while( (d1 = getchar()) != '\n' ){ if( d1 >= 'a' && d1 <= 'z' ){ cin >> d2; consts[d2-'a'][d1-'a'] = true; } }//while get constraints if(flag == true) puts(""); sort_vars(0, vars.size()-1); //sort variables vector<char> tmp; comb(tmp, vars); //produce combinations //initialize flag = true; vars.clear(); for(i=0; i<MAX_LET; i++) for(j=0; j<MAX_LET; j++) consts[i][j] = false; }//get constraints } return 0; } void sort_vars(int left, int right){ if( left < right ){ int i = left + 1; int j = right; while(1){ for(; (i<=right) && (vars[i] <= vars[left]); i++); for(; (j>left) && (vars[j] > vars[left]); j--); if( i>=j ) break; swap(vars[i], vars[j]); } swap(vars[j], vars[left]); sort_vars(left, j-1); sort_vars(j+1, right); } } void comb(vector<char> current, vector<char> pool){ vector<char>::size_type i, j; if( pool.empty() ){ for(i=0; i!=current.size(); i++) cout << current[i]; cout << endl; return; } vector<char> tmp_cur, tmp_pool; vector<char>::size_type psize = pool.size(); for(i=0; i<psize; i++){ for(j=0; j<psize; j++){ if( consts[ pool[i]-'a' ][ pool[j]-'a' ] ) break; } if( j == psize ){ tmp_pool = pool; tmp_cur = current; tmp_cur.push_back(pool[i]); tmp_pool.erase(tmp_pool.begin()+i); comb(tmp_cur, tmp_pool); } }//i return; }
No comments:
Post a Comment