1 #if !defined HAVE_PARTITION_2FALL_ASC_H__ 2 #define HAVE_PARTITION_2FALL_ASC_H__ 3 // This file is part of the FXT library. 4 // Copyright (C) 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 "comb/is-partition-asc.h" 9 10 #include "comb/comb-print.h" 11 #include "comb/print-partition-aa.h" 12 13 #include "fxttypes.h" 14 15 16 #define PARTITION_2FALL_ASC_FIXARRAYS // default on 17 // speedup with GCC 4.9.0 18 19 20 class partition_2fall_asc 21 // Partitions of n is a partition a[1] + a[2] + ... + a[m] = n 22 // such that a[k] >= 2 * a[k-1]. 23 // Representation as weakly ascending list of parts. 24 // Lexicographic order. 25 // Cf. OEIS sequence A000929. 26 // Equinumerous to s-partitions (partitions into Mersenne numbers), 27 // cf. class partition_s_desc. 28 { 29 public: 30 ulong n_; // integer partition of n 31 ulong m_; // current partition has m parts 32 #ifndef PARTITION_2FALL_ASC_FIXARRAYS 33 ulong *a_; // partition: a[1] + a[2] + ... + a[m] = n 34 #else 35 ulong a_[62]; 36 #endif 37 38 partition_2fall_asc(const partition_2fall_asc&) = delete; 39 partition_2fall_asc & operator = (const partition_2fall_asc&) = delete; 40 41 private: mers_t(ulong s)42 ulong mers_t(ulong s) 43 // Return greatest t such that 2^t-1 <= s. 44 { 45 ulong t = 0; 46 ulong b = 1; 47 while ( s+1 > b ) { ++t; b <<= 1; } 48 49 if ( s < b-1 ) { --t; b >>= 1; } 50 51 return t; 52 } 53 54 public: partition_2fall_asc(ulong n)55 explicit partition_2fall_asc(ulong n) 56 { 57 n_ = n; 58 ulong k = 1; 59 if ( n_ != 0 ) k += mers_t(n_); 60 #ifndef PARTITION_2FALL_ASC_FIXARRAYS 61 a_ = new ulong[k]; 62 #endif 63 first(); 64 } 65 ~partition_2fall_asc()66 ~partition_2fall_asc() 67 { 68 #ifndef PARTITION_2FALL_ASC_FIXARRAYS 69 delete [] a_; 70 #endif 71 } 72 data()73 const ulong * data() const { return a_ + 1; } 74 num_parts()75 ulong num_parts() const { return m_; } 76 first()77 void first() 78 { 79 a_[0] = 0; // unused 80 m_ = 0; 81 if ( n_ == 0 ) return; 82 ulong y = 1, s= n_; 83 do 84 { 85 ++m_; 86 a_[m_] = y; 87 s -= y; 88 y *= 2; 89 } 90 while ( s >= y ); 91 a_[m_] += s; 92 } 93 next()94 ulong next() 95 // Return number of parts of generated partition. 96 // Return zero if the current is the last partition. 97 { 98 if ( m_ <= 1 ) return 0; // current is last 99 100 ulong y = a_[m_-1], s = y + a_[m_]; 101 y += 1; 102 --m_; 103 while ( s >= y ) 104 { 105 a_[m_] = y; 106 ++m_; 107 s -= y; 108 y *= 2; 109 } 110 --m_; 111 a_[m_] += s; 112 113 return m_; 114 } 115 116 117 void print(const char *bla, bool dfz=false) const 118 { print_vec(bla, data(), num_parts(), dfz); } 119 print_aa()120 void print_aa() const // ASCII art 121 { print_partition_asc_aa(data(), m_); } 122 print_conj_aa()123 void print_conj_aa() const // ASCII art 124 { print_partition_asc_conj_aa(data(), m_); } 125 126 OK()127 bool OK() const 128 { 129 if ( ! is_partition_asc(data(), num_parts(), n_) ) return false; 130 131 for (ulong j=2; j<=m_; ++j) // a[j] >= 2 * a[j-1] ? 132 if ( a_[j] < 2 * a_[j-1] ) return false; 133 134 return true; 135 } 136 }; 137 // ------------------------- 138 139 140 #endif // !defined HAVE_PARTITION_2FALL_ASC_H__ 141