Discreture

This is a modern C++14 library designed to facilitate combinatorial research by providing fast and easy iterators to a few combinatorial objects, such as combinations, permutations, partitions, and others. The idea is to have discreture's lazy containers interface resemble the STL containers as much as possible, by providing the standard ways of iterating over them.

In addition, many of the algorithms described in the standard <algorithm> library work as-is in these containers, as if the containers were marked as const.

This library is provided as a header-only library and has been tested on Linux. Other operating systems might work. Let me know if you find any issues!

Quick preview:

#include <iostream>
#include <discreture.hpp>

using discreture::operator<<;

int main()
{
    for (auto&& x : discreture::combinations(5,3))
        std::cout << x << std::endl;
    
    return 0;
}

The above code would produce the following output:

0 1 2
0 1 3
0 2 3
1 2 3
0 1 4
0 2 4
1 2 4
0 3 4
1 3 4
2 3 4

You need to compile with the -std=c++14 flag: g++ -std=c++14 -O3 main.cpp

Installation

Discreture is a header-only library and its only dependency is boost. Programs using it need to be compiled with c++14 or later. Tested with gcc 5.4.0 and clang 3.9.0 and up. Other compilers might work too.

To use, simply make sure your programs have access to the .hpp files (all files inside "include" dir). Just copy them to your project's include folders or tell your compiler where to look.

Install with package manager

For easy integration, Discreture can be installed through VCPKG. Simply run vcpkg install discreture.

Pre-requisites for compiling

Nothing needs to be compiled. But if you wish to build examples, benchmarks and tests, these are the pre-requisites.

• A C++ compiler (i.e. gcc or clang)
• boost (header files. Specifically: iterator_facade)
• cmake or meson
• git (only for downloading the directory. You can also download it directly from gitlab/github)
• Google's Test Framework (for building unit tests only).

Starting from v1.9 we also support the much faster meson build system instead of cmake, but shall continue to maintain support for cmake.

Installing pre-requisites in Ubuntu Linux and derivatives

sudo apt-get install libboost-all-dev git build-essential cmake

Installing pre-requisites in Arch Linux and derivatives

sudo pacman -S boost git gcc cmake

Installing pre-requisites in mac OS

First, make sure HomeBrew is installed. Then in a terminal do:

brew install gcc cmake git boost

Install discreture

To do a system-wide install, do the standard cmake/make dance:

git clone --recursive https://gitlab.com/miguelraggi/discreture.git
cd discreture
mkdir build
cd build
cmake ..
make
sudo make install

This will install the necessary headers under /usr/local/ by default. If you wish to install to some other directory, replace the cmake .. above by something like cmake .. -DCMAKE_INSTALL_PREFIX=/usr/.

There are three options: BUILD_EXAMPLES, BUILD_TESTS and BUILD_BENCHMARKS. To use discreture you don't need to compile anything, but if you wish to, you can compile examples, tests and benchmarks by replacing the cmake .. part by:

cmake .. -DBUILD_EXAMPLES=ON -DBUILD_TESTS=ON -DBUILD_BENCHMARKS=ON

By default, nothing is built, as discreture is a header-only library.

Trying the examples

After compiling the examples (with cmake .. -DBUILD_EXAMPLES=ON), try for example running:

./combinations 5 3

This will output all combinations of size 3 from the set {0,1,2,3,4}.

Or try for example

./combinations "abcde" 3

will output all subsets of size 3 of "abcde".

There are many other example programs there. Play with them.

How to start using the library

To use the library, after compiling, just add #include <discreture.hpp> to your project and make sure you are compiling in c++14 mode (or later). With the GCC compiler this can be done by compiling like this: g++ -std=c++14 myfile.cpp. You can include only part of the library, say, combinations, by adding #include <Discreture/Combinations.hpp> for example.

Combinatorial Objects

Within this library, one can construct a few combinatorial objects, such as:

• Combinations: Subsets of a specific size of either a given set or {0,1,...,n-1}:
  • Example: {0,3,4}, {0,1,5} in combinations(6,3)
  • Example2: {'a','b','c'}, {'a','c','d'} in combinations("abcdef"s,3)
• Permutations: A permutation of a collection is a reordering of all the elements of C.
  • Example: [0,1,2], [2,0,1] in permutations(3)
  • Example2 : ['a','b','c'], ['c','a','b'] in permutations("abc"s)
• Partitions: Numbers that add up to a given number.
  • Example: {6,4,1}, {3,3,3,1,1} in partitions(11)
• Set Partitions: Partitions of {0,...,n-1} into disjoint sets.
  • Example: { {0,2}, {1,3} } in set_partitions(4)
• Multisets: How many to take of each index?
  • Example: {2,1,3}, {0,1,1} in multisets([3,1,3])
• Dyck Paths: From (0,0) to (2n,0) but y is never negative and always goes either up or down.
  • Example: [1,1,-1,1,-1,-1] in dyck_paths(3). Note no partial sum is less than 0.
• Motzkin Paths: Like dyck paths but allowing 0's.
  • Example: [1,0,-1,1,1,-1,0,-1] in motzkin_paths(9)
• Integer Intervals: A (lazy) closed-open interval of integers.
  • Example: integer_interval(4,8) = {4,5,6,7}
• Arithmetic Progression: A (lazy) set of the form {a,a+d,a+2d,...,a+kd}.
  • Example: {1,4,7} in arithmetic_progression(1,8,3)

All follow the same design principle: The templated class is called SomethingOrOther<...>, with CamelCase notation, and there is either a function or a typedef for the simplest template parameters. However, most of the time you'll be using the small_case_notation version, which either is a typedef or a function with sensible parameters.

For example, partitions is a typedef of Partitions<int, vector<int>>, but combinations is a function with two versions, depending on the arguments. It returns either an object of type Combinations<T, vector<T>> or IndexedViewContainer</*some template parameters*/>, depending on which arguments are passed. Note that there is currently no support for detecting repeats, so combinations("aabc"s,2) has ab two times. If you need this functionality, let me know and I'll do my best to implement it quickly.

Some tests show that on different machines different types produce faster code, so even if you don't need numbers bigger than 127 it might be a good idea to use int or long rather than char.

Basic usage

auto X = discreture::combinations(30,10); //all subsets of size 10 of {0,1,2,...,29}
for (auto&& x : X) 
{ 
    // x is of type const vector<int>&, so anything that works with 
    // const vector references also works on x, such as indexing, iterating, etc. x[3], etc.
}

Reverse iterators are defined too.

discreture::Combinations<short> X(30,10);
for (auto it = X.rbegin(); it != X.rend(); ++it) 
{ 
    auto& x = *it;
}

But of course there is a simpler way:

auto X = permutations(10);
for (auto&& x : reversed(permutations)) 
{ 
    // do stuff to x.
}

Combinations, Permutations and Multisets are random-access containers so something like this works too:

auto X = discreture::combinations(30,10);
auto comb = X[10000]; //produces the 10,000-th combination.

Warning: Please note that it is much slower if one plans to actually iterate over all of them à la

for (int i = 0; i < X.size(); ++i)
{ 
    // use X[i] 
}

so don't do that.

However, iterator arithmetic is implemented, so one could even do binary search on X with the following code:

#include <algorithm>
// ...
auto X = discreture::combinations(30,10);
std::partition_point(X.begin(), X.end(), predicate);

where predicate is a unary predicate that takes a const combinations::combination& as an argument and returns true or false, in a way that for all the first combinations it returns true and the last ones return false.

This is also useful to use many processors at once. See tutorial_parallel.cpp under "examples" on how to do this.

Tutorial

Here is a quick mini-tutorial. See the examples for more on usage. Check the files under examples for a more complete tutorial on how to use the library. Maybe start with the file called tutorial.cpp and then read the others in any order.

Combinations example

After installing, let's start by creating a file called "combinations.cpp" and adding the following content:

#include <iostream>
#include <string>
#include <discreture.hpp> // just include everything

using namespace std::string_literals;
using discreture::operator<<;

int main()
{
    for (auto&& x : discreture::combinations("abcde"s,3))
    {
        std::cout << x << std::endl;
    }
    return 0;
}

This prints out: a b c a b d