Tuesday, January 13, 2015

[sqniubpu] De Bruijn play

Modify The Blue Room (David Hare) / Der Reigen / La Ronde (Arthur Schnitzler) play such that all pairs of characters interact.

A De Bruijn sequence is the starting point but it has flaws: characters get paired with themselves and order matters.  Ideally meet all these constraints:

* Only heterosexual pairs of characters, preserving the ability for the play to be done with only 2 actors. (Or, in general, a complete bipartite matching.)
* All heterosexual pairs at least once.
* All heterosexual pairs at most once.
* One character stays on stage during each scene change.
* The character who has been on stage longer leaves at the end of each scene (FIFO).

Looks like it's possible for 2 male and 2 female; impossible for 3 male and 3 female.

Upon further thought, this is simply a Eulerian circuit through a complete bipartite graph, so possible when there are even numbers on both sides. A small task is to come up with an algorithm to output one of the Eulerian circuits.

Calling back to the original title of the play, it could be a way to organize a partnered dance exhibition, allowing each possible couple a spotlight and a "steal" as a transition. Into which position of the queue does the exiting dancer go? What should be the initial order of the queue?

No comments :