+/* In-place cyclic permutation of a container (no copying, only swapping). */
+template <class It, class Swap>
+void cyclic_permutation(It first, It last, It new_first, Swap swapit)
+{
+ unsigned num = last - first;
+again:
+ if (first == new_first || num < 2)
+ return;
+
+ unsigned num1 = new_first - first, num2 = last - new_first;
+ if (num1 >= num2) {
+ It a = first, b = new_first;
+ while (b != last) {
+ swapit(*a, *b);
+ ++a; ++b;
+ }
+ if (num1 > num2) {
+ first += num2;
+ num = num1;
+ goto again;
+ }
+ } else {
+ It a = new_first, b = last;
+ do {
+ --a; --b;
+ swapit(*a, *b);
+ } while (a != first);
+ last -= num1;
+ num = num2;
+ goto again;
+ }
+}
+
+/** Base class for generating all bounded combinatorial partitions of an integer
+ * n with exactly m parts in non-decreasing order.
+ */
+class basic_partition_generator {
+protected:
+ // Partitions n into m parts, not including zero parts.
+ // (Cf. OEIS sequence A008284; implementation adapted from Jörg Arndt's
+ // FXT library)
+ struct mpartition2
+ {
+ // partition: x[1] + x[2] + ... + x[m] = n and sentinel x[0] == 0
+ std::vector<unsigned> x;
+ unsigned n; // n>0
+ unsigned m; // 0<m<=n
+ mpartition2(unsigned n_, unsigned m_)
+ : x(m_+1), n(n_), m(m_)
+ {
+ for (unsigned k=1; k<m; ++k)
+ x[k] = 1;
+ x[m] = n - m + 1;
+ }
+ bool next_partition()
+ {
+ unsigned u = x[m]; // last element
+ unsigned k = m;
+ unsigned s = u;
+ while (--k) {
+ s += x[k];
+ if (x[k] + 2 <= u)
+ break;
+ }
+ if (k==0)
+ return false; // current is last
+ unsigned f = x[k] + 1;
+ while (k < m) {
+ x[k] = f;
+ s -= f;
+ ++k;
+ }
+ x[m] = s;
+ return true;
+ }
+ };
+ mpartition2 mpgen;
+ basic_partition_generator(unsigned n_, unsigned m_)
+ : mpgen(n_, m_)
+ { }
+};
+
+/** Generate all bounded combinatorial partitions of an integer n with exactly
+ * m parts (including zero parts) in non-decreasing order.
+ */
+class partition_with_zero_parts_generator : public basic_partition_generator {
+private:
+ unsigned m; // number of parts 0<m
+ mutable std::vector<unsigned> partition; // current partition
+ mutable bool current_updated; // whether partition vector has been updated
+public:
+ partition_with_zero_parts_generator(unsigned n_, unsigned m_)
+ : basic_partition_generator(n_, 1), m(m_), partition(m_), current_updated(false)
+ { }
+ // returns current partition in non-decreasing order, padded with zeros
+ const std::vector<unsigned>& get() const
+ {
+ if (!current_updated) {
+ for (unsigned i = 0; i < m - mpgen.m; ++i)
+ partition[i] = 0; // pad with zeros
+
+ for (unsigned i = m - mpgen.m; i < m; ++i)
+ partition[i] = mpgen.x[i - m + mpgen.m + 1];
+ }
+ return partition;
+ }
+ bool next()
+ {
+ current_updated = false;
+ if (!mpgen.next_partition()) {
+ if (mpgen.m == m || mpgen.m == mpgen.n)
+ return false; // current is last
+ // increment number of parts
+ mpgen = mpartition2(mpgen.n, mpgen.m + 1);
+ }
+ return true;
+ }
+};
+
+/** Generate all bounded combinatorial partitions of an integer n with exactly
+ * m parts (not including zero parts) in non-decreasing order.
+ */
+class partition_generator : public basic_partition_generator {
+private:
+ mutable std::vector<unsigned> partition; // current partition
+ mutable bool current_updated; // whether partition vector has been updated
+public:
+ partition_generator(unsigned n_, unsigned m_)
+ : basic_partition_generator(n_, m_), partition(m_), current_updated(false)
+ { }
+ // returns current partition in non-decreasing order, padded with zeros
+ const std::vector<unsigned>& get() const
+ {
+ if (!current_updated) {
+ for (unsigned i = 0; i < mpgen.m; ++i)
+ partition[i] = mpgen.x[i + 1];
+ }
+ return partition;
+ }
+ bool next()
+ {
+ current_updated = false;
+ return mpgen.next_partition();
+ }