Permutation and Combination

combination.cc

#include <vector>
#include <iostream>

using namespace std;

void vec_print(const vector<int> &v){
  cout << "[ ";
  for(vector<int>::const_iterator itr = v.begin();
      itr != v.end(); ++itr){
    cout << *itr << " ";
  }
  cout << "]" << endl;
}

void permute0(size_t i, vector<int> &used, vector<int> &path, const vector<int> &v){
  if(i == v.size()){
    vec_print(path);
    return;
  }
  for(int j = 0; j < int(v.size()); j++){
    if(used[j] != 1){
      used[j] = 1;
      path.push_back(v[j]);
      permute0(i+1,used,path,v);
      path.pop_back();
      used[j] = 0;
    }
  }
}

void permute(const vector<int> &v){
  vector<int> path, used(v.size());
  permute0(0,used,path,v);
}

void combi0(size_t i, int j, vector<int> &path, const vector<int> &v, int r){
  if(j == r){
    vec_print(path);
    return;
  }
  if(i == v.size()){
    return;
  }

  path.push_back(v[i]);
  combi0(i+1,j+1,path,v,r);
  path.pop_back();
  combi0(i+1,j,path,v,r);
}

void combi(const vector<int> &v, int r){
  vector<int> path;
  combi0(0,0,path,v,r);
}


int main(int argc, char *argv[]){
  ios::sync_with_stdio(false);
  int a[] = {1,2,3,4,5};
  vector<int> v(a,a+5);
  cout << "permutation example" << endl;
  permute(v);
  cout << "combination example" << endl;
  combi(v,3);
  return 0;
}