On Feb 27, 8:47 pm, Michael Robertson <[EMAIL PROTECTED]> wrote: > Michael Robertson wrote the following on 02/27/2008 06:40 PM: > > > Hi, > > > I need a generator which produces all ways to place n indistinguishable > > items into k distinguishable boxes. > > My first thought was to generate all integer partitions of n, and then > generate all permutations on k elements. So:
Two more cents: > 4 = 4 > = 3 + 1 > = 2 + 2 > = 2 + 1 + 1 And if |x|> k, discard it. For k= 1, you'd stop after 4 = 4. <Reads below.> Ah, you said that. Also make sure you stop at floor( k/ 2 ), so you don't get 4 = 1 + 3. > Then for 4, generate all permutations of x=(4,0,0,..), |x|=k > Then for 3,1 generate all permutations of x=(3,1,0,..), |x|=k > Then for 2,2 generate all permutations of x=(2,2,0...), |x|=k > ... Your only casualty here is all the zeroes in (4,0,0,..). You don't want to swap k_2 and k_3 in (4,0,0). (Is that what permutation means?) > In addition to having to generate permutations for each integer > partition, I'd have to ignore all integer partitions which had more than > k parts...this seemed like a bad way to go (bad as in horribly inefficient). > > Better ideas are appreciated. Running time on my recursive was K** 2* N, counting the copy, I think. sum( 1..i )== i( i+ 1 )/ 2, O( i** 2 ). My iterative was slower, K** 3* N, unless you save a K or N in the small length of K early on, I think. Did anyone take this course that can tell me? -- http://mail.python.org/mailman/listinfo/python-list
