1 #if !defined HAVE_PERM_TROTTER_LG_H__ 2 #define HAVE_PERM_TROTTER_LG_H__ 3 // This file is part of the FXT library. 4 // Copyright (C) 2010, 2011, 2012, 2014, 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 #include "aux0/swap.h" 9 #include "comb/comb-print.h" 10 #include "fxttypes.h" 11 12 13 class perm_trotter_lg 14 // Gray code for permutations 15 // Trotter/Johnson algorithm. 16 // Largest element moves most often. 17 { 18 public: 19 ulong n_; // number of elements to permute 20 ulong *xi_; // inverse permutation 21 ulong *x_; // permutation of {0, 1, ..., n-1} 22 ulong *d_; // auxiliary: directions 23 ulong sw1_, sw2_; // indices of elements swapped most recently 24 25 perm_trotter_lg(const perm_trotter_lg&) = delete; 26 perm_trotter_lg & operator = (const perm_trotter_lg&) = delete; 27 28 public: perm_trotter_lg(ulong n)29 explicit perm_trotter_lg(ulong n) 30 { 31 n_ = n; 32 xi_ = new ulong[n_+2]; 33 x_ = new ulong[n_+2 + (n_==0)]; 34 d_ = new ulong[n_+2]; 35 36 ulong sen = n_; // sentinel value maximal 37 x_[0] = x_[n_+1] = sen; 38 39 ++x_; 40 first(); 41 } 42 ~perm_trotter_lg()43 ~perm_trotter_lg() 44 { 45 --x_; 46 delete [] xi_; 47 delete [] d_; 48 delete [] x_; 49 } 50 51 private: small_n()52 void small_n() 53 // Make cases n==0 and n==1 work. 54 { 55 if ( n_ <= 1 ) 56 { 57 x_[0] = 0; x_[1] = 1; 58 xi_[0] = 0; xi_[1] = 1; 59 d_[0] = 0; d_[1] = 0; 60 } 61 } 62 63 public: first()64 void first() 65 { 66 for (ulong i=0; i<n_; i++) xi_[i] = i; 67 for (ulong i=0; i<n_; i++) x_[i] = i; 68 for (ulong i=0; i<n_; i++) d_[i] = -1UL; 69 sw1_ = 0; sw2_ = 1; // relative to last permutation 70 small_n(); 71 } 72 last()73 void last() 74 { 75 for (ulong i=0; i<n_; i++) xi_[i] = i; 76 for (ulong i=0; i<n_; i++) x_[i] = i; 77 for (ulong i=0; i<n_; i++) d_[i] = +1; 78 sw1_ = 0; sw2_ = 1; // relative to first permutation 79 d_[sw1_] = -1UL; 80 d_[sw2_] = -1UL; 81 swap2(x_[sw1_], x_[sw2_]); 82 swap2(xi_[sw1_], xi_[sw2_]); 83 small_n(); 84 } 85 next()86 bool next() 87 { 88 ulong e1 = n_; 89 while ( e1-- ) 90 { 91 // e1 is the element we try to move 92 ulong i1 = xi_[e1]; // position of element e1 93 ulong d = d_[e1]; // direction to move e1 94 ulong i2 = i1 + d; // position to swap with 95 ulong e2 = x_[i2]; // element to swap with 96 97 if ( e1 > e2 ) // can we swap? 98 { 99 xi_[e1] = i2; 100 xi_[e2] = i1; 101 x_[i1] = e2; 102 x_[i2] = e1; 103 sw1_ = i1; sw2_ = i2; 104 while ( ++e1<n_ ) d_[e1] = -d_[e1]; 105 return true; 106 } 107 } 108 109 first(); 110 return false; 111 } 112 113 prev()114 bool prev() 115 { 116 ulong e1 = n_; 117 while ( e1-- ) 118 { 119 // e1 is the element we try to move 120 ulong i1 = xi_[e1]; // position of element e1 121 ulong d = -d_[e1]; // direction to move e1 (NOTE: negated) 122 ulong i2 = i1 + d; // position to swap with 123 ulong e2 = x_[i2]; // element to swap with 124 125 if ( e1 > e2 ) // can we swap? 126 { 127 xi_[e1] = i2; 128 xi_[e2] = i1; 129 x_[i1] = e2; 130 x_[i2] = e1; 131 sw1_ = i1; sw2_ = i2; 132 while ( ++e1<n_ ) d_[e1] = -d_[e1]; 133 return true; 134 } 135 } 136 137 last(); 138 return false; 139 } 140 data()141 const ulong * data() const { return x_; } invdata()142 const ulong * invdata() const { return xi_; } get_swap(ulong & s1,ulong & s2)143 void get_swap(ulong &s1, ulong &s2) const { s1=sw1_; s2=sw2_; } 144 145 void print(const char *bla, bool dfz=false) const 146 // If dfz is true then Dots are printed For Zeros. 147 { print_perm(bla, data(), n_, dfz); } 148 149 void print_inv(const char *bla, bool dfz=false) const 150 // If dfz is true then Dots are printed For Zeros. 151 { print_perm(bla, invdata(), n_, dfz); } 152 }; 153 // ------------------------- 154 155 156 157 #endif // !defined HAVE_PERM_TROTTER_LG_H__ 158