[Python-ideas] Include partitioning in itertools

[Tim Peters]

[Albert ten Oever]
> ...
> I want to propose to include a 'partition' (mathematically more correct: a
> set partition) function in itertools.
>
> To my knowledge, partitioning of a set (iterable) is quite a common thing to
> do and a logic extension of the combinatoric generators in itertools.
>
> It is implemented as a Python recipe
> (http://code.activestate.com/recipes/576795-partitioning-a-sequence/).


[Sven R. Kunze]
> ...
> Not quite sure if I understand the implementation. Reading this
> http://mathworld.wolfram.com/BellNumber.html for the given example of 6, it
> should have 203 possible partitions. What am I missing?

The ActiveState recipe has nothing to do with set partitions.  Instead
it returns all ways of breaking a sequence into a sequence of
subsequences whose sum (catenation) is the original sequence.  If
there are N elements in the original sequence, there are 2**(N-1) ways
to do that.  That's why there are 32 results in the recipe's example
output (2**(len("abcdef")-1) == 32).  There would be 203 "set
partitions" of a 6-element set.