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