Beefy Boxes and Bandwidth Generously Provided by pair Networks
XP is just a number

Re: Powerset short-circuit optimization

by BrowserUk (Pope)
on Oct 03, 2006 at 19:38 UTC ( #576173=note: print w/replies, xml ) Need Help??

in reply to 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.

Replies are listed 'Best First'.
Re^2: Powerset short-circuit optimization
by Limbic~Region (Chancellor) on Oct 03, 2006 at 21:42 UTC
    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

Log In?

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://576173]
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others browsing the Monastery: (2)
As of 2020-10-25 14:21 GMT
Find Nodes?
    Voting Booth?
    My favourite web site is:

    Results (249 votes). Check out past polls.