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 in and out swap values for
one or two items on each iteration.

Quick Start

1. Include the revdoor.hpp header.
2. For combinations without replacement, initialize a generator object with
   revdoor::combinations. For combinations with replacement, initialize a
   generator object with revdoor::combinations_with_replacement.
3. Use the state() method to get the initial state of the generator.
4. Call the step() method to proceed to the next combination.
   • For combinations without replacement, this takes two int pointers:
     out‘s dereference is set to the element that is removed, and in‘s
     dereference is set to the element that is added.
   • For combinations without replacement, this takes four int pointers:
     out1‘s and out2‘s dereferences are set to elements that are removed;
     in1‘s and in2‘s dereferences are set to elements that are added.
     In cases where only a single item is swapped out, *out1 == *in1.

Example 1: combinations without replacement

#include <revdoor.hpp>
#include <vector>
void process_init_state(const std::vector<int> init_state) { /* ... */ }
void process_change(int out, int in) { /* ... */ }
int main(int argc, char* argv[]) {
  int n = 5;
  int t = 3;
  revdoor::combinations combs(n, t);
  std::vector<int> init_state = combs.state();
  process_init_state(init_state);
  int out, in;
  while (combs.step(&out, &in)) {
    process_change(out, in);
  }
  return 0;
}

Example 2: combinations with replacement

#include <revdoor.hpp>
#include <vector>
void process_init_state(const std::vector<int> init_state) { /* ... */ }
void process_change(int out, int in) { /* ... */ }
int main(int argc, char* argv[]) {
  int n = 5;
  int t = 3;
  revdoor::combinations_with_replacement combs_rep(n, t);
  std::vector<int> init_state = combs_rep.state();
  process_init_state(init_state);
  int out1, in1, out2, in2;
  while (combs_rep.step(&out1, &in1, &out2, &in2)) {
    if (out1 != in1)
      process_change(out1, in1);
    process_change(out2, in2);
  }
  return 0;
}

Documentation

Refer to the comments in revdoor.hpp for detailed information.

License

The source code has an MIT License.

See revdoor.hpp.

References

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