Beefy Boxes and Bandwidth Generously Provided by pair Networks
Syntactic Confectionery Delight

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 ;)


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?

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://458606]
and all is quiet...

How do I use this? | Other CB clients
Other Users?
Others drinking their drinks and smoking their pipes about the Monastery: (3)
As of 2017-05-28 15:35 GMT
Find Nodes?
    Voting Booth?