revdoor

revdoor is a single-file C++ library for visiting revolving door combinations.

The combinations without replacement generator implements Algorithm R from TAOCP 7.2.1.3 [1]. The combinations with replacement generator implements the same algorithm, modified to support replacement.

The algorithms visit combinations by indicating at most two pairs of items to swap in and out on each iteration.

The source code is available on GitHub:
https://github.com/dstein64/revdoor

Example

The following example program—that uses the revdoor single-file header library—visits combinations by indicating the replacement for each iteration. For the purpose of illustration, the full set of combination items is tracked and printed on each iteration.

	#include <cassert>
	#include <cstdlib>
	#include <iostream>
	#include <set>
	#include <string>
	#include <vector>
	#include "revdoor.hpp"
	using namespace std;
	void print_set(const set<int>& s) {
	set<int>::iterator it = s.begin();
	while (it != s.end()) {
	if (it != s.begin()) cout << ",";
	cout << *(it++);
	}
	cout << endl;
	}
	int main(int argc, char* argv[]) {
	assert(argc == 3);
	int n = stoi(argv[1]);
	int t = stoi(argv[2]);
	revdoor::combinations combs(n, t);
	vector<int> init_state = combs.state();
	set<int> state(init_state.begin(), init_state.end());
	cout << "init: ";
	print_set(state);
	int in, out;
	while (combs.step(&out, &in)) {
	cout << "out: " << out << ", in: " << in << " state: ";
	state.erase(out);
	state.insert(in);
	print_set(state);
	}
	return EXIT_SUCCESS;
	}

view raw revdoor.cpp hosted with ❤ by GitHub

An example usage is shown below.

$ ./example 5 3
init: 0,1,2
out: 1, in: 3 state: 0,2,3
out: 0, in: 1 state: 1,2,3
out: 2, in: 0 state: 0,1,3
out: 1, in: 4 state: 0,3,4
out: 0, in: 1 state: 1,3,4
out: 1, in: 2 state: 2,3,4
out: 3, in: 0 state: 0,2,4
out: 0, in: 1 state: 1,2,4
out: 2, in: 0 state: 0,1,4

References

[1] Donald Knuth, The Art of Computer Programming, Volume 4, Fascicle 3: Generating All Combinations and Partitions (Addison-Wesley Professional, 2005).