StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>Define P(n) as the number of ways to partition n, restricting n to be an integer, n >= 1.</p> <p>Define p(n, k) as the number of ways to partition n using numbers no larger than k, restricting k to be an integer, k >= 1, k <= n.</p> <p>It follows that P(n) = sum (i: 1..n) p(n, i).</p> <p>To find p(n, k), first note that we neatly avoid double-counting by simply keeping the partition sorted: take the largest chunk first. So the first chunk may have any size from 1 up to k, and then the rest of the chunks must account for the rest of the total n, and be no larger than the first chunk.</p> <p>Thus p(n, k) = sum (i: 1..k) p(n - i, i).</p> <p>As a base case, p(1, 1) = 1.</p> <hr> <p>A sample implementation, very much <strong>not</strong> guaranteed to be at all efficient, or even to compile (but it should give you the basic idea) - spoilers!</p> <pre><code>// A utility function to represent the result of appending to a vector, // as a new vector (without affecting the previous one). template <typename T> vector<T> operator<<(vector<T> copy, T to_append) { // We passed by value to get a copy implicitly. copy.push_back(to_append); return copy; } // A utility function to append one vector to another. template <typename T> vector<T>& operator+=(vector<T>& original, const vector<T>& to_append) { // 'copy' is in namespace std:: and defined in <algorithm>. // 'back_inserter' is in namespace std:: and defined in <iterator>. copy(to_append.begin(), to_append.end(), back_inserter(original)); return original; } vector<vector<int> > partitions(int remaining, int limit, vector<int> prefix) { // Finds the partitions of some larger number which start with the // numbers in 'prefix', such that the rest of the "chunks" sum to // 'remaining' and are all no larger than 'limit'. // 'max' is in namespace std:: and defined in <algorithm>. We restrict // the 'limit' to be no more than 'remaining'. limit = max(remaining, limit); vector<vector<int> > result; // Base case. if (remaining == 1) { return result << (prefix << 1); // note the parentheses are required! } for (int i = limit; i > 0; --i) { result += partitions(remaining - i, i, prefix << i); } return result; } </code></pre>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload