In search of an algorithm for sorting collection in nodes to satisfy a layout constraint

Question

Firstly, I apologize for the poor title; I cannot think of a good name for this algorithm.

I have an ordered list of stages. Each stage has a cast of characters, unordered. Characters can occur in multiple stages.

A crossing occurs when two consecutive stages cannot have their casts concatenated, with overlap allowed where it would unify the same character on both casts, in a way that leaves a character duplicated in the concatenation. Or, informally, a crossing is when a character would need to be at two different spots at once in a line-up of the combined casts. In code:

uncrossed = [D, F], [N, V, S]
overlap = [D, F, V], [V, N, S]
crossed = [D, V, F], [N, V, S]

In the first example, V isn't with D and F, so there aren't any crossings. In the second example, V is with D and F and then with N and S, but this isn't a problem because the ordering permits (with overlap) a crossing-less concatenation. On the third example, though, the ordering forces a crossing.

For my purposes, crossings can occur on non-consecutive stages as if characters did not actually stray from their previous order in the cast when they are not "on-stage."

I would like to order each stage's cast such that there are as few crossings as possible, understanding that it is definitely possible to have situations where crossings are inevitable. An example series which requires crossings:

required = [A, B], [B, C], [A, C], [A, B]

This all sounds very abstract and silly, so I'll provide a concrete example of a human solving this algorithm for a purpose similar to mine: http://xkcd.com/657/ In this case, the constraint is deliberately ignored for aesthetic purposes, but it's still possible to get a visual idea of what I'm talking about.

I already have some crude ideas for how to solve this, but nothing affordable, and I'm wondering if this is isomorphic to some problem already covered in the literature. It sounds vaguely topological as well.

Since people asked, this algorithm appears to be key to automatically generating pretty timelines for storyboards of characters in stories, and that's what I'm intending to use it for.

Answer 1

This isn't an answer, but I think maybe a more precise or even more correct formulation of what you are looking for:

There is a set, call it C, of characters, and there is a finite ordered sequence S_1, ... S_n of scenes, where a scene is a set consisting of some of the characters. Characters may (and typically do) appear in multiple scenes.

I'd like to phrase your desired outcome in a slightly different way from how you phrased it, because I think it makes it clearer how one may search for a solution (or at least, it makes it totally clear how to brute-force a solution):

The output of our algorithm is a sequence of arrangements of the characters. An arrangement of the characters is just a permutation of the ordered tuple [c_1, ... c_m], where the c_i are the characters, and there are m of them in total, so C = {c_1, ..., c_m}. We want n arrangements in total, call them A_1, ..., A_n, one per scene.

What arrangement A_n corresponds to is the top-to-bottom ordering of the characters in your storyboard, during scene n, in the following sense: draw a vertical line through your storyboard passing through scene n. This line should hit the characters' life-lines in the order specified by A_n.

We require the following property of our arrangements: given scene S_n, the arrangement A_n needs to put the characters contained in S_n into a contiguous chunk, in the following sense: suppose that S_n = {c_2, c_3, c_5}. Then A_n may yield [c_1, c_4, c_2, c_3, c_5], but may not yield [c_2, c_1, c_3, c_4, c_5]. This is because you don't want an errant character "cutting through" the scene in the storyboard.

We hope to minimize the number of "crossings." Here, crossings are easy to define: the number of crossings between A_i and A_(i+1) is exactly equal to the number of transpositions of adjacent characters required to go from permutation A_i to permutation A_(i+1).

---

I haven't given you an answer, but I think that given the above setup, a brute-force approach isn't too hard to code up, and will give you an answer overnight without a problem, if the storyboard isn't too big.

I think that if you posted this problem on MathOverflow, you could possibly get someone interested in it. Or maybe it has been solved, who knows?