On May 24, 2006, at 4:37, Ken Williams wrote:
That algorithm works, but it's overkill for this example, though. It generates all possible partitions into 2 sets, which is O(2^ {n-1}) partitions (see http://en.wikipedia.org/wiki/ Stirling_number_of_the_second_kind), but if we want just the ones with partition sizes k & n-k, that can be done in O(n-choose-k) which can be quite a bit less (depending on n and k).
Sure, thank you. In my view this thread has two topics: partitions, and the original problem. Generating combinations and computing complements was already suggested for the latter. That last code was only meant to show off the use of the new partitions().
-- fxn
