Re: List partitioning

I wrote :
...might be worth the while to consider the space of unions of n>1 groups, whose optimization (ie splitting into n specific groups), can be achieved independently of that of their complement set.

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


Although I never tried it, if you go that route I would suggest trying tabled predicates as is provided by XSB and B-prolog, with the vague idea that they could permit to write the search as a relatively simple-minded systematic computation, leaving to the system the task of recognizing and skipping a repeated sub-computation (to the point of changing the asymptotic behavior).

Cheers, BB
.

Relevant Pages

  • Re: "ZIP Attacks with Reduced Known-Plaintext"
    ... After every scrolls divide by 0x08088405 ... code to see if it opens. ... It appear to be a two's complement shifted ...
    (sci.crypt)
  • Re: "ZIP Attacks with Reduced Known-Plaintext"
    ... zip files with probably 50 or more known plain text bytes that are ... After every scrolls divide by 0x08088405 ... It appear to be a two's complement shifted ... two's complement  number encryption. ...
    (sci.crypt)
  • Re: Shift Operation
    ... To divide by 2? ... mostly mathematically useless. ... i.e. shift of -1 on a two's complement ...
    (comp.lang.c)
  • Re: sign magnitude, ones complement, twos complement
    ... >> two's complement ... >> What are the pitfalls of them? ... > I doubt if sign magnitude has ever been used in a popular US computer. ... Multiply and divide are easier in sign magnitude, ...
    (comp.lang.c)