Beefy Boxes and Bandwidth Generously Provided by pair Networks
Perl: the Markov chain saw
 
PerlMonks  

Re: Powerset short-circuit optimization

by grinder (Bishop)
on Oct 03, 2006 at 16:48 UTC ( #576122=note: print w/replies, xml ) Need Help??


in reply to Powerset short-circuit optimization

You can think of elements within a powerset being chosen or not according to a bit vector. 5 elements requires five bits.

You start at 00000, so your powerset has no elements.

Then you increment, and get 00001. Thus, you take the last element. Some time later, after having incremented the counter for a while, you get to 01101, so you take the second, third and fifth elements.

Finally, you get to 11111, and you take all elements. And then you stop.

This is how my module Data::PowerSet is implemented (except that it starts at 11111 and counts down. Looking at the implementation, I don't see an aha! solution to make it jump over a region, but I'm sure with a savant dose of binary and'ing and or'ing you could make it do that.

Patches welcome!

• another intruder with the mooring in the heart of the Perl

  • Comment on Re: Powerset short-circuit optimization

Replies are listed 'Best First'.
Re^2: Powerset short-circuit optimization
by Limbic~Region (Chancellor) on Oct 03, 2006 at 16:57 UTC
    grinder,
    Yes, I am very familiar with iterative methods at generating a powerset. I am also familiar with generating them in a certain order such that you can "jump" over a region. What I can't figure out how to do is generate them in the specific order that I would most benefit from in this situation. I do have an idea about using multiple iterators to generate the powerset itself instead of a single one. I am playing with that idea now.

    Cheers - L~R

Log In?
Username:
Password:

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

How do I use this? | Other CB clients
Other Users?
Others surveying the Monastery: (4)
As of 2020-10-21 02:10 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?
    My favourite web site is:












    Results (212 votes). Check out past polls.

    Notices?