Software Project based on the article 'Fast Algorithms for Finding Pattern Avoiders and Counting Pattern Occurrences in Permutations' [1].
[1] William Kuszmaul, https://arxiv.org/abs/1509.08216
Makefile is placed in directory ./rp.
Program has two main parts:
-
tests.cpp — Test of correctness compared to sequences in data.txt; build and run with
make tests && make tt
. -
main.cpp — For testing on user defined pattern sets; build with
make main
. Demo:
$ cd ./rp
$ make main
g++ -Wall -pthread -std=c++1z -O3 -march=native main.cpp -o main
$ ./main <<EOF
> 1243
> 4231
> EOF
Pattern set: { 3120 0132 }
Avoiding sequence: 0 1 2 6 22 86 335 1266 4598 16016
$ make clean
find . | sed -e 's/\.cpp//' | sort | uniq -d | tee /dev/stderr | xargs rm
./main
Both main.cpp and tests.cpp containst two compile-time parameters;
constexpr auto LETTER = 4;
constexpr auto SIZE = 10;
denoting maximum size of given permutation which container
rp::Permutation<LETTER,SIZE>
can holds and number of bits spended on each letter of given permutation. Therfore SIZE
determines the maximum length of sequence generated in previous demo.
- Project is written in C++14; few last commits require C++17 standard.
- Tested on clang/macOS, clang/Linux and gcc 6.3/Linux