ACM: 124 – Following Orders

真開心再用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;
}