Beefy Boxes and Bandwidth Generously Provided by pair Networks
Just another Perl shrine
 
PerlMonks  

Re: Recursively-generated Iterators

by blokhead (Monsignor)
on May 19, 2005 at 13:09 UTC ( #458606=note: print w/ replies, xml ) Need Help??


in reply to Recursively-generated Iterators

Quite an interesting technique, and as a disclaimer I really do like it. That being said, this technique will not always get you the fastest iterator. The holy grail of iterators for combinatorial structures is a constant amortized time (CAT) algorithm, meaning that any N successive calls to the iterator takes O(N) time. This is as good as it gets.

Your technique is great as the iterator algorithm mirrors the easy-to-understand recursive algorithm. And kudos for noting (and fixing) the double-recursion. However, your algorithm's running time for iterating through all (N choose K) combinations is proportional to (N+2 choose K+1), so it is not CAT. For a detailed analysis of this and many other interesting iteration algorithms, see section 4.3 of the book Combinatorial Generation by Frank Ruskey. The book does give a CAT iterator for generating combinations, and I believe your general technique of mirroring the recursive algorithm inherently cannot achieve CAT running time (unless you memoize, which defeats the whole purpose of iterating to save memory).

I guess it's a matter of what you want to trade -- (sometimes small) factors of running time, or readability of the algorithm. Although for iteration problems like this, I usually just refer to Ruskey's book and find a pre-packaged CAT algorithm ;)

blokhead


Comment on Re: Recursively-generated Iterators
Re^2: Recursively-generated Iterators
by Roy Johnson (Monsignor) on May 19, 2005 at 17:37 UTC
    You can go a little further and say that this technique will never get you the fastest iterator, but it will likely get you one that is fast and memory-efficient enough, while remaining simple: a sweet spot.

    Caution: Contents may have been coded under pressure.

Log In?
Username:
Password:

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

How do I use this? | Other CB clients
Other Users?
Others avoiding work at the Monastery: (14)
As of 2015-07-02 18:33 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    The top three priorities of my open tasks are (in descending order of likelihood to be worked on) ...









    Results (44 votes), past polls