PatternTransitionTables

PatternTransitionTables Library
🌸 Part of GoemonYae Trading System (GYTS) 🌸


🌸 --------- 1. INTRODUCTION --------- 🌸

💮 Overview
This library provides precomputed state transition tables to enable ultra-efficient, O(1) computation of Ordinal Patterns. It is designed specifically to support high-performance indicators calculating Permutation Entropy and related complexity measures.

💮 The Problem & Solution
Calculating Permutation Entropy, as introduced by Bandt and Pompe (2002), typically requires computing ordinal patterns within a sliding window at every time step. The standard successive-pattern method (Equations 2+3 in the paper) requires ≤ 4d-1 operations per update.

Unakafova and Keller (2013) demonstrated that successive ordinal patterns "overlap" significantly. By knowing the current pattern index and the relative rank (position l) of just the single new data point, the next pattern index can be determined via a precomputed look-up table. Computing l still requires d comparisons, but the table lookup itself is O(1), eliminating the need for d multiplications and d additions. This reduces total operations from ≤ 4d-1 to ≤ 2d per update (Table 4). This library contains these precomputed tables for orders d = 2 through d = 5.


🌸 --------- 2. THEORETICAL BACKGROUND --------- 🌸

💮 Permutation Entropy
Bandt, C., & Pompe, B. (2002). Permutation entropy: A natural complexity measure for time series.
https://doi.org/10.1103/PhysRevLett.88.174102

This concept quantifies the complexity of a system by comparing the order of neighbouring values rather than their magnitudes. It is robust against noise and non-linear distortions, making it ideal for financial time series analysis.

💮 Efficient Computation
Unakafova, V. A., & Keller, K. (2013). Efficiently Measuring Complexity on the Basis of Real-World Data.
https://doi.org/10.3390/e15104392

This library implements the transition function φ_d(n, l) described in Equation 5 of the paper. It maps a current pattern index (n) and the position of the new value (l) to the successor pattern, reducing the complexity of updates to constant time O(1).


🌸 --------- 3. LIBRARY FUNCTIONALITY --------- 🌸

💮 Data Structure
The library stores transition matrices as flattened 1D integer arrays. These tables are mathematically rigorous representations of the factorial number system used to enumerate permutations.

💮 Core Function: get_successor()
This is the primary interface for the library for direct pattern updates.
• Input: The current pattern index and the rank position of the incoming price data.
• Process: Routes the request to the specific transition table for the chosen order (d=2 to d=5).
• Output: The integer index of the next ordinal pattern.

💮 Table Access: get_table()
This function returns the entire flattened transition table for a specified dimension. This enables local caching of the table (e.g. in an indicator's init() method), avoiding the overhead of repeated library calls during the calculation loop.

💮 Supported Orders & Terminology
The parameter d is the order of ordinal patterns (following Bandt & Pompe 2002). Each pattern of order d contains (d+1) data points, yielding (d+1)! unique patterns:
• d=2: 3 points → 6 unique patterns, 3 successor positions
• d=3: 4 points → 24 unique patterns, 4 successor positions
• d=4: 5 points → 120 unique patterns, 5 successor positions
• d=5: 6 points → 720 unique patterns, 6 successor positions

Note: d=6 is not implemented. The resulting code size (approx. 191k tokens) exceeds the Pine Script limit of 100k tokens (as of 2025-12).