generate all partitions of a set [closed]

There is an important observation (in a comment) that a partition of a set of n elements can be represented as an integer sequence of the form [p₁, … p_n] where p_i is the partition number of element i. For such a sequence to be valid, it must obey the rules that p₁ is 1, and for every j where 1 < j ≤ n, there is some i < j such that p_j ≤ p_i&plus;1. Or in other words, in any prefix of the sequence, no integer is skipped.

Now, there is a standard algorithm for enumerating constrained sequences in lexicographical order, which consists of the following:

• Start with the smallest sequence.
• To find the next sequence in lexicographical order:
  • Scan backwards over the sequence and find the rightmost “incrementable” element. (An incrementable element is an element such that there is some larger element which could be substituted for that element, and the resulting subsequence up to that point is a prefix of at least one valid sequence.)
  • Change that element to the next larger element which is viable (i.e. which results in a valid prefix, as above), and then fill in the remaining elements to its right (if any) with the smallest possible values.
  • If there is no incrementable element, then the enumeration has terminated.

With several provisions about the search for an incrementable element, this algorithm is at worst O(n) and it is often O(1) when the element to be incremented is usually close to the end of the sequence. (For example, using this algorithm to enumerate permutation is O(1) to find the next permutation as long as you can find the “next element” in O(1).)

In order to apply this algorithm to the partition case, we observe the following:

1. The smallest possible sequence is [1, … 1]
2. An element p_i is incrementable provided that:
   • p_i<n
   • There is some j<i such that p_i&equals;p_j
3. The smallest suffix of a viable prefix is [1, … 1]

Another way of stating the condition in observation 2 is that an element is incrementable unless its value is n or it is the first element in the sequence with its value. We can make that determination in O(1) if we also maintain the sequence [m₁, … m_n] where m₁ is 0, and m_i is the maximum of m_i-1 and p_i-1. m is trivial to maintain, and it allows us to rewrite the incrementability condition as simply p_i≤m_i.

It is easy to see that Next Partition can be implemented in O(n) time, but as it happens it is also the case that it is amortized time O(1). Roughly speaking, that is because in most cases, the last element of the sequence is incrementable.