1 #if !defined HAVE_CATALAN_STEP_RGS_SUBSET_LEXREV_H__ 2 #define HAVE_CATALAN_STEP_RGS_SUBSET_LEXREV_H__ 3 // This file is part of the FXT library. 4 // Copyright (C) 2012, 2013, 2014, 2015, 2019 Joerg Arndt 5 // License: GNU General Public License version 3 or later, 6 // see the file COPYING.txt in the main directory. 7 8 9 #include "comb/is-catalan-step-rgs.h" 10 #include "comb/print-catalan-step-rgs-aa.h" 11 12 #include "comb/comb-print.h" 13 14 #include "fxttypes.h" 15 16 #define CATALAN_STEP_RGS_SUBSET_LEXREV_FIXARRAYS // default on 17 18 class catalan_step_rgs_subset_lexrev 19 // Catalan step RGS (restricted growth strings), subset-lexrev order. 20 // RGS are a[] such that a[k] >= a[k-1] (weakly ascending) and a[k]<=k. 21 // The RGS describe lattice paths from (0,0) to (n,n) with steps 22 // (+1,0) and (+1,+1) that do not go below the diagonal. 23 // Same as: rising factorial numbers where the digits are sorted. 24 // See Joerg Arndt, Subset-lex: did we miss an order?, (2014) 25 // http://arxiv.org/abs/1405.6503 26 { 27 public: 28 #ifndef CATALAN_STEP_RGS_SUBSET_LEXREV_FIXARRAYS 29 ulong *a_; // RGS 30 #else 31 ulong a_[64]; 32 #endif 33 ulong n2_; // aux: min(n,2). 34 ulong tr_; // aux: track we are looking at 35 ulong n_; // length of RGS 36 37 catalan_step_rgs_subset_lexrev(const catalan_step_rgs_subset_lexrev&) = delete; 38 catalan_step_rgs_subset_lexrev & operator = (const catalan_step_rgs_subset_lexrev&) = delete; 39 40 public: catalan_step_rgs_subset_lexrev(ulong n)41 explicit catalan_step_rgs_subset_lexrev(ulong n) 42 { 43 n_ = n; 44 n2_ = (n>=2 ? n : 2); // make things work with n<=1 45 #ifndef CATALAN_STEP_RGS_SUBSET_LEXREV_FIXARRAYS 46 a_ = new ulong[n2_+1]; 47 #endif 48 a_[0] = 0; 49 a_[n2_] = n2_; // sentinel 50 // layout of a[]: 51 // [0, 1, 2, 3, ..., n-1, n ] index 52 // [0, *, *, *, ..., *, n ] value 53 54 first(); 55 } 56 ~catalan_step_rgs_subset_lexrev()57 ~catalan_step_rgs_subset_lexrev() 58 { 59 #ifndef CATALAN_STEP_RGS_SUBSET_LEXREV_FIXARRAYS 60 delete [] a_; 61 #endif 62 } 63 data()64 const ulong * data() const { return a_; } 65 first()66 void first() 67 { 68 for (ulong k=1; k<n2_; ++k) a_[k] = 0; 69 tr_ = n2_ - 1; 70 if ( n_ <= 1 ) 71 { 72 tr_ = 1; 73 a_[1] = 1; 74 } 75 } 76 77 // void last() 78 // { 79 // for (ulong k=1; k<n2_; ++k) a_[k] = 1; 80 // tr_ = n2_ - 1; 81 // if ( n_ <= 1 ) 82 // { 83 // tr_ = 1; 84 // a_[1] = 0; 85 // } 86 // } 87 next()88 ulong next() 89 // Return position of *rightmost* change (1,...,n-1). 90 // Return zero if current RGS is last. 91 // Either one digit is changed, or the range T0, ..., T1 where 92 // T0 is the return value of the last call to next() and 93 // T1 the return value of the current call to next(). 94 { 95 const ulong a0 = a_[tr_]; 96 97 if ( a0 < a_[tr_+1] ) // may read sentinel 98 { 99 if ( a0 < tr_ ) // can increment 100 { 101 a_[tr_] = a0 + 1; 102 return tr_; 103 } 104 } 105 106 if ( tr_ != 1 ) // can move left and increment (from 0 to 1) 107 { 108 --tr_; 109 a_[tr_] = 1; 110 return tr_; 111 } 112 113 // remove ones: 114 ulong j = tr_; 115 do { a_[j] = 0; } while ( a_[++j] == 1 ); 116 117 if ( j==n2_ ) return 0; // current was last 118 119 // decrement first value != 1: 120 ulong aj = a_[j] - 1; 121 a_[j] = aj; 122 123 // move left and restore the 1: 124 tr_ = j - 1; 125 a_[tr_] = 1; 126 return j; // rightmost change at j==tr+1 127 } 128 129 // ulong prev() 130 // { 131 // const ulong a0 = a_[tr_]; 132 // if ( a0 == 0 ) return 0; // current is first 133 // const ulong a1 = a_[tr_+1]; 134 // } 135 136 print(const char * bla,bool dfz)137 void print(const char *bla, bool dfz) const 138 { print_vec(bla, a_, n_, dfz); } 139 print_aa()140 void print_aa() const // ASCII art 141 { catalan_step_rgs_print_aa(data(), n_); } 142 OK()143 bool OK() const 144 { return is_catalan_step_rgs(data(), n_); } 145 }; 146 // ------------------------- 147 148 149 #endif // !defined HAVE_CATALAN_STEP_RGS_SUBSET_LEXREV_H__ 150