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?