#include <vector>
#include <iostream>
#include <cassert>

using namespace std;

class Perm {
  vector<int> as;
  int now = -1;
  Perm* p = NULL;

public:

  void nextp() {
    if(p) delete p;

    if(++now < as.size()) {
      vector<int> as_(as);
      as_.erase(as_.begin()+now);
      p = new Perm(as_);
    }
  }

  Perm(vector<int> &as_) {
    as = as_;
    if(as.size() == 1) now = 0;
    else nextp();
  }

  vector<int> * next() {
    if(as.size() == 1) {
      now++;
      return new vector<int>(as);
    } else {
      vector<int> *ret = p->next();
      ret->push_back(as[now]);
      if(p->end()) nextp();
      return ret;
    }
  }

  bool end() { return as.size() <= now; }
};

int main()
{
  vector<int> as = {1,2,3};
  Perm perm(as);

  while(!perm.end()) {
    vector<int> *seq = perm.next();

    // use seq
    for(int i=0; i<seq->size(); i++)
      cout << (*seq)[i] << ' ';
    cout << endl;

    delete seq;
  }
}