Re: List partitioning

bim wrote:
Boris Borcic a écrit :
I fear this isn't clear enough. A natural illustration would be the topmost reduction of a search for an optimal partition of N items into P groups where P does /not/ divide N, into searches over all ways of distributing the N items into complementary subsets of N' and N'' items, to divide in turn (this time /evenly/) into P' and P'' groups respectively.

Where N',N'',P' and P'' are fixed as a function of N and P, ie

P' = N mod P
P'' = P - P'
N' = ((N//P)+1)*P'
N'' = (N//P)*P''

For each choice of distribution of N items into N'- and N''-sized subsets, the further optimal partition of each of these complementary subsets can then proceed independently (I think, given your description of the problem).

So, if I understood correctly, let's say I have 10 items to split into 4 groups. I should first list all the ways of distributing these 10 items into 2 groups (6 items + 4 items). Then for each of these partitions, I should look for the best way to partition the group of 6 items into 2 sub-groups, and the group of 4 items into 2 sub-groups too. And finally keep the best full partition among all these partitions ? Would this be really faster ? I guess you mean that I would have to exclude some top-level paritions (ie: 6/4) first because they wouldn't lead to suitable full-partitions anyway ?

What you "should" do I don't really know, it's more a "could". I think actual counting is in order. If you count in this case, you see that there are 6300 distinct partitions, while there are 210 ways to split the 10 items into 4+6, and in each case 3 ways to further split the 4 items and 10 ways to further split the 6 items, and since 6300 == 210*3*10, this means exactly the same number of cases to consider.

OTOH, the case of 16 items split into 8 groups of 2 implies looking at 2027025 distinct partitions, while first splitting 16 items into 8+8 and each in turn 4+4 and each in turn 2+2 while caching results implies looking once at each 2-set (120 of them), once at each 4-set (1820 of them) times the ways to divide 4-sets into 2-sets (3 of them), once at each 8-set (12870 of them) times the ways to divide 8-sets into 4-sets (35 of them), and once at each way to divide the 1 initial 16-set into 8-sets (6435 of them).

What gives us 120+1820*3+12870*35+6435 = 462465 partial situations to consider each quite simpler than a complete partition, of which there are 2027025. 462465/2027025 ~ 23%.

Ok, like for FFT the case where you can evenly divide your universe of items by a power of 2 is the best possible situation, but this doesn't mean you can't exploit some of the same effect in other situations.

Cheers, BB
.

Relevant Pages

  • Re: Philosphy of programming
    ... > advance (I'll partition my reality in such a way that the ... > different parts will only interact in predefined ways, ... Then divide those and so on. ...
    (comp.programming)
  • Re: Grouping Into 1/2 Hour Time Buckets
    ... raskew wrote: ... The third posting uses the partition() function and breaks it down into 15 ... Divide by 450 instead 900 for 1/2 hour periods. ...
    (microsoft.public.access.queries)
  • Re: nee help please reinstalling xp with new partitions
    ... not sure why it would boot into the CD set up while it was in the ... maybe it will make things easier to divide it up a bit... ... I'd say to set the C: drive for at least 40 gigs or so ... There is no way to expand a partition in XP? ...
    (microsoft.public.windowsxp.help_and_support)
  • Re: List partitioning
    ... topmost reduction of a search for an optimal partition of N items into P groups where P does /not/ divide N, into searches over all ways of distributing the N items into complementary subsets of N' and N'' items, to divide in turn into P' and P'' groups respectively. ... For each choice of distribution of N items into N'- and N''-sized subsets, the further optimal partition of each of these complementary subsets can then proceed independently. ...
    (comp.lang.prolog)