Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

Make your likes visible on Facebook?

Connect your Facebook account to Prezi and let your likes appear on your timeline.
You can change this under Settings & Account at any time.

No, thanks

Combinatorial Generation - A Coroutine Based Approach

A presentation on using coroutines to approach combinatorial generation objects, with examples in Python
by

Sahand Saba

on 6 August 2014

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of Combinatorial Generation - A Coroutine Based Approach

Combinatorial Generation
A Coroutine Based Approach
Presentation by Sahand Saba
sahands@gmail.com

What are coroutines?
"Subroutines are special cases of coroutines."
- Donald Knuth
Subroutines
A freezes
Execution passes to B
B finishes
Execution passes back to A
A thaws and continues from where it left off
A
B
A calls B
Subroutines are Asymmetric
A is the "main" routine
B is the "sub" routine
Coroutines
Any coroutine can pass execution to any other
Each coroutine maintains its own state separately (no stack)
Coroutines can freeze and wait for another coroutine to pass execution back to them
A
G
Symmetric generalization of subroutines
Example 1: The generator pattern
G is the
generator
yields
items
A uses the generator
Calls G to get the
next
object
Coroutines
Next
Next
Next
Yield
Yield
Yield
P
C
Example 2: The consumer-producer pattern
C is the
consumer
requires data availability
P is the
producer
produces or gathers data
(In some sense, this is the dual of the generator pattern.)
Coroutines
Send
Send
Send
More
More
More
Example 3: Event loops and event handlers
EL is the
event loop
listens for events and invokes handlers based on the event
H[1], ..., H[1] are
handlers
handle an event and return execution to the event loop
Coroutines
EL
H[2]
H[3]
H[1]
Call
Return
Coroutines in Python
Implemented using the enhanced
yield
keyword
Details in PEP 342
We will not cover "send", "raise" and other more advanced aspects of the implementation
Only need "yield" and "next" for our purposes!
Let's go over the basics
Coroutines in Python
Instead of return,
yield
Functions with the keyword yield in them become coroutines
When called, they return a new "instance" of the coroutine
In this sense, they act more like classes
Note 1: You are now responsible for looping
Note 2: Coroutines need not terminate.
Example 1: Fibonacci numbers
Example 2.a: Simple permutations
Example 2.b: Permutations usage
But... wait a second!
Isn't that first example really just iterative solution?
And isn't the second example just the recursive solution?
"... cats and dogs living together... mass hysteria!" - Dr. Peter Venkman
So what does this mean?
Coroutines are a generalization of subroutines.
As such any iterative or recursive algorithm can be implemented using them.
In fact, there is a trivial implementation of any iterative or recursive generation algorithm using coroutines, as demonstrated in the two previous examples.
Combinatorial Generation Using Coroutines
So is that all?
Not quite, we can use coroutines in more creative ways for combinatorial generation.

Let's look at some examples.
Example 3.a: SJT Permutation Generation
SJT Permutation Generation Using Coroutines
Basic Idea
Permuting 1, ..., n
n coroutines: coroutines[i] for 1<= i <= n
coroutine[i] keeps moving i to the left, until it reaches a number that is larger than i
Then switches direction and passes execution to coroutine[i - 1]
Coroutines yield True if they have more to generate
coroutine[0] and coroutine[n + 1] are special: they always yield False
Example 3.b: SJT Coroutine Setup
SJT Permutation Generation Using Coroutines
Some Observations
Simplicity of the recursive solution
But the efficiency of the iterative solution (well, in theory anyway!)
Setting everything up is a bit tricky
A correct choice of a "lead" coroutine is key
False is yielded by the lead coroutine when all permutations are generated
But we can continue calling, and the permutations will be generated in reverse order
Example 4: Gray Code Generation
Gray Code Generation
Basic Idea
To use Knuth's description:
Imagine a line of n friendly trolls
Each troll carries a light that is either on or off
Each troll is also either awake or asleep
When poked the troll:
If awake: switches his light from off to on
If asleep: wakes up and pokes the next troll in line
Exercise: convince yourself that this produces the binary reflected gray code!
Let's look at another example.
Based on methods and ideas in
Deconstructing Coroutines
by Donald Knuth and Frank Ruskey

Let's look again.
Code available at: https://github.com/sahands/coroutine-generation
Gray Code Generation
Some Observations
Deceivingly simple code!
In this example we created the coroutines as needed, instead of creating all of them in advance
Can be generalized to generate ideals of a poset in gray order
Let's look at the zig zag poset as an example.
Example 5.a: Ideals of The Zig Zag Poset
Example 5.a: Ideals of The Zig Zag Poset
Conclusions
Coroutines be used to implement iterative and recursive combinatorial generation algorithms
But also more creative "somewhere between recursive and iterative" algorithms
Thank you!
Full transcript