Re: Powerset short-circuit optimization

Would it be right to conclude that (assuming an efficient generator that doesn't generate duplicates), that you will only achieve this optimisation when generating multiple (related) powersets?

That is, in your second example,

there is no optimisation possible when generating set1.
It is only possible to optimise the generation of set2 if that set is ordered such that some part of it forms an ordered subset of set1
Ie. If set2 were E, C, B, A, no optimisation would be possible?

Or, can the code assume that the sets are pre-ordered? Or should it sort them?

Or does the definition of powersets imply some ordering?

Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.

Lingua non convalesco, consenesco et abolesco. -- Rule 1 has a caveat! -- Who broke the cabal?

"Science is about questioning the status quo. Questioning authority".

In the absence of evidence, opinion is indistinguishable from prejudice.

Comment on Re: Powerset short-circuit optimization Select or Download Code

Replies are listed 'Best First'.
Re^2: Powerset short-circuit optimization by Limbic~Region (Chancellor) on Oct 03, 2006 at 21:42 UTC
BrowserUk, You can assume the input set will be ordered alphabetically so your Ie. should not apply. You are also correct that no optimization is possible for a set that has no intersection with a previously generated powerset. If this doesn't answer all of your questions, please let me know. Cheers - L~R	[reply]


Syntactic Confectionery Delight
	PerlMonks