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

Re^3: Powerset short-circuit optimization

by tilly (Archbishop)
on Oct 04, 2006 at 22:08 UTC ( #576428=note: print w/replies, xml ) Need Help??

in reply to Re^2: Powerset short-circuit optimization
in thread Powerset short-circuit optimization

Let me say what my code does, and what it doesn't do.

It generates the subsets in the exact order that the original post gave, and does so in a way in which you can easily skip all subsets of the current subset. Furthermore it does this with bounded memory requirements, and with somewhat reasonable performance. However it does not guarantee that it generates all longer sets before generating a short set.

If you wish to guarantee that it generates all longer sets before generating a short set, then you'll have to explicitly remember all of the skips you were asked to make (with potentially large memory requirements to do that), and the skipping step is going to become very complex. Limbic-Region will have to confirm one way or another, but I think I made the performance tradeoff that he would want.

  • Comment on Re^3: Powerset short-circuit optimization

Replies are listed 'Best First'.
Re^4: Powerset short-circuit optimization
by Limbic~Region (Chancellor) on Oct 04, 2006 at 22:56 UTC
    I was hoping to guarantee all the longer sets were processed first by ordering them according to length. Unfortunately I have discovered that this will not be possible in the larger problem space this is to help solve.

    I am very happy to have your code though even if I can't use it this time. I am sure it will come in handy in the future or at a minimum - I will learn a lot from it.

    Cheers - L~R

Log In?

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

How do I use this? | Other CB clients
Other Users?
Others wandering the Monastery: (4)
As of 2020-10-27 13:03 GMT
Find Nodes?
    Voting Booth?
    My favourite web site is:

    Results (256 votes). Check out past polls.