Skip to content

Instantly share code, notes, and snippets.

@bivoje
Created April 16, 2019 03:44
Show Gist options
  • Save bivoje/0e615cfce5efa9881c8a26b4e6a3dc6f to your computer and use it in GitHub Desktop.
Save bivoje/0e615cfce5efa9881c8a26b4e6a3dc6f to your computer and use it in GitHub Desktop.
cpp permutation generator class in python style
#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;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment