set partitioning

[James Waldby]

"hymort at hotmail.com" wrote:
> Can someone tell me of a good algorithm to partition a set of n
> elements into m non-empty, disjoint subsets, where each subset has
> size k?

and later wrote in a separate post
> Also, if I do not care about the number of subsets, what is a good
> algorithm to partition a set of n elements into non-empty, disjoint
> subsets of size k?

and then execrably wrote [ie, top-posted]: 
> Not quite what I'm looking for.  I would like a list of all partitions
> with each partition having k or less elements, not just one instance.

when Aaron Watters wrote:
> Something like this, or am I missing something?
> 
> def partition(List, n, m, k):
[snip Watters' program to partition set of n elements
 into m non-empty disjoint subsets, each of size k]

So if n=3 and k=2 and set S={a,b,c}, you would want a list
like the following?
1.  {a},{b},{c}
2.  {a,b},{c}
3.  {a,c},{b}
4.  {b,c},{a}

So it appears you need to do 2 things -

(1) Produce a list of additive partitions of n with numbers
not exceeding k.  In the S={a,b,c} example, the list contains
(1,1,1) and (2,1).  I think you can make the list with work
O(T(n,k)).  For values of T(n,k) (ie, "number of partitions of 
n in which the greatest part is k, 1<=k<=n") see
http://www.research.att.com/~njas/sequences/A008284 .

(2) For each list from (1), fill in elements from S into each
of the subsets, in canonical order.  (Eg, after filling in (1,1,1) 
to make {a},{b},{c}, don't produce {a},{c},{b} etc.)  See a
combinatorial algorithms book, eg Reingold, for this part.
http://www.amazon.com/gp/product/013152447X/104-5966364-8396722?n=283155

-jiw