Re: List partitioning

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 ?
.

Relevant Pages

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