**Combinatorial Generation**

**A Coroutine Based Approach**

**Presentation by Sahand Saba**

sahands@gmail.com

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

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!