1 #if !defined HAVE_MPARTITION_H__ 2 #define HAVE_MPARTITION_H__ 3 // This file is part of the FXT library. 4 // Copyright (C) 2010, 2012, 2013, 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 9 #include "fxttypes.h" 10 11 class mpartition 12 // Partitions into m parts. 13 // Representation as list of parts in weakly ascending order. 14 // Cf. OEIS sequence A008284. 15 // Same functionality as class mpartition2, which 16 // avoids the auxiliary array s[]. 17 { 18 public: 19 ulong *x_; // partition: x[1] + x[2] + ... + x[m] = n 20 ulong *s_; // aux: cumulative sums of x[] (s[0]=0) 21 ulong n_; // integer partitions of n (must have n>0) 22 ulong m_; // ... into m parts (must have 0<m<=n) 23 24 mpartition(const mpartition&) = delete; 25 mpartition & operator = (const mpartition&) = delete; 26 27 public: mpartition(ulong n,ulong m)28 explicit mpartition(ulong n, ulong m) 29 // Must have n >= 1 and 1 <= m <= n. 30 { 31 n_ = n; 32 m_ = m; 33 x_ = new ulong[m_+1]; 34 s_ = new ulong[m_+1]; 35 first(); 36 } 37 ~mpartition()38 ~mpartition() 39 { 40 delete [] x_; 41 delete [] s_; 42 } 43 data()44 const ulong * data() const { return x_+1; } 45 first()46 void first() 47 { 48 x_[0] = 0; // sentinel 49 for (ulong k=1; k<m_; ++k) x_[k] = 1; 50 x_[m_] = n_ - m_ + 1; 51 ulong s = 0; 52 for (ulong k=0; k<=m_; ++k) { s+=x_[k]; s_[k]=s; } 53 } 54 next()55 bool next() 56 { 57 ulong u = x_[m_]; // last element 58 ulong k = m_; 59 while ( --k ) { if ( x_[k] + 2 <= u ) break; } 60 61 if ( k==0 ) return false; // current is last 62 63 ulong f = x_[k] + 1; 64 ulong s = s_[k-1]; 65 while ( k < m_ ) 66 { 67 x_[k] = f; 68 s += f; 69 s_[k] = s; 70 ++k; 71 } 72 x_[m_] = n_ - s_[m_-1]; 73 // s_[m_] = n_; // unchanged 74 75 return true; 76 } 77 }; 78 // ------------------------- 79 80 81 #endif // !defined HAVE_MPARTITION_H__ 82