# set partitioning

Boris Borcic bborcic at gmail.com
Tue May 2 09:52:01 EDT 2006

I wrote:
>
> def pickk(k,N,m=0) :
>     if k==1 :
>         return ((n,) for n in range(m,N))
>     else :
>         return ((n,)+more for more in pickk(k-1,N,m+1)
>                           for n in range(m,more[0]))
>
> def partitionN(k,N) :
>     subsets = [frozenset(S) for S in pickk(k,N)]

while it doesn't otherwise change results, changing this line to

subsets = [frozenset(S) for S in sorted(pickk(k,N))]

provides everything nicely ordered (e.g. lexicographically)

>     def exhaust(rest,bound=0) :
>         if len(rest) < k :
>             if rest :
>                 yield [sorted(rest)]
>             else :
>                 yield []
>         for newbound in range(bound,len(subsets)) :
>             S = subsets[newbound]
>             if rest >= S :
>                 sS = [sorted(S)]
>                 for restpart in exhaust(rest-S,newbound+1) :
>                     yield sS+restpart
>     return exhaust(set(range(N)))
>
> partition = lambda k,S : [[[S[j] for j in S0] for S0 in P0]
>                                  for P0 in partitionN(k,len(S))]
>
>  >>> partition(2,[1,2,3,4])
> [[[1, 2], [3, 4]], [[1, 3], [2, 4]], [[2, 3], [1, 4]]]
>  >>> partition(3,[1,2,3,4])
> [[[1, 2, 3], [4]], [[1, 2, 4], [3]], [[1, 3, 4], [2]], [[2, 3, 4], [1]]]
>
>
> CAVEAT : insufficiently tested, not proved correct, uncommented,
> provided as is