set partitioning

[Boris Borcic]

hymort at hotmail.com wrote:
> For the list [1,2,3,4], I'm looking for the following for k = 2:
> 
> [[1,2], [3,4]]
> [[1,3], [2,4]]
> [[1,4], [2,3]]
> 
> for k = 3:
> 
> [[1,2,3], [4]]
> [[1,2,4], [3]]
> [[1,3,4], [2]]
> [[2,3,4], [1]]
> 

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)]
     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