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