Categories
Uncategorized

🚪 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.

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).

Leave a Reply

Your email address will not be published. Required fields are marked *