Beefy Boxes and Bandwidth Generously Provided by pair Networks
go ahead... be a heretic
 
PerlMonks  

Re: Recursively-generated Iterators

by blokhead (Monsignor)
on May 19, 2005 at 13:09 UTC ( [id://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

Replies are listed 'Best First'.
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
Domain Nodelet?
Node Status?
node history
Node Type: note [id://458606]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this?Last hourOther CB clients
Other Users?
Others lurking in the Monastery: (6)
As of 2024-04-18 22:26 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found