Declarations of functions associated with group_G.
Version of Thursday 26 September 2024.

These support pattern matching. The count_pattern_ functions tell how many times a pattern appears in a permzbi. The has_pattern_ functions quit as soon as they find one example, and will thus often run in less time than the count_pattern_. Meanwhile, the is_ functions rely on the has_pattern_ functions.

    static bool constexpr pattern_verbose {true};

    /* G2 */ int count_pattern (SVI const & pattern) const;
    /* G2 */ bool has_pattern (SVI const & pattern) const;

The next three functions are optimized to find patterns of length three, four, or five, where the pattern is known at compile time; it is indicated by the template parameters. They should run faster than the non-_quick has_pattern functions, because the compiler can evaluate many of the expressions they contain. Throughout the literature, patterns of length three or four are the most widely discussed.

    /* G3 */ template <int Q, int R, int S>
             bool has_pattern_quick () const;
    /* G3 */ template <int Q, int R, int S, int T>
             bool has_pattern_quick () const;
    /* G3 */ template <int Q, int R, int S, int T, int U>
             bool has_pattern_quick () const;

The _pattern_cycle functions also have a _quick version, but they reside in group_H because of the amount of code required.

The next seven functions are direct support for some patterns and combinations that are metioned in the literature.

    /* G3 */ bool is_stack_sortable () const;
    /* G3 */ bool is_separable () const;
    /* G3 */ bool is_layered () const;
    /* G3 */ bool is_gilbreath () const;
    /* G3 */ bool is_vexillary () const;
    /* G3 */ bool is_riffle () const;
    /* G3 */ bool is_skew_merged () const;

The two functions below will find the specified pattern, but only when it appears among consecutive components of a permzbi. By contrast, all the functions above accept nonconsecutivity.

    /* G4 */ int  count_pattern_consec (SVI const & pattern) const;
    /* G4 */ bool has_pattern_consec (SVI const & pattern) const;

The pattern submitted to count_pattern_ or has_pattern need not be a permzbi. Instead, it can be any sequence of pairwise distinct integers; they need not be consecutive or nonnegative. For example, vexillary permutations avoid the pattern that is usually written 2143. However, any pattern abcd meeting all six of the following inequalities will give the same result in this program:

b < a

b < c

b < d

a < c

a < d

d < c

An example, written with commas for clarity, is (−6, −8, 14, 11).

The function below tells whether, within a permzbi, every component (other than the first and last) is either greater than its predecessor and successor, or less than both.

    /* G4 */ bool is_craggy () const;