<p>我不太确定,但我想你想要的是:</p>
<ul>
<li>开始时间相同的不同行上的位移是同步的,即水平位置相同(每行的第一个位移与其他行的第一个位移同步)</li>
<li>具有相同<strong>开始时间的“真实”事件和间隙是同步的</strong>,并且在具有相同开始时间的位移之后</li>
<li>事件的宽度取决于它的持续时间(可能还有它的位移),但是<strong>不是</strong>取决于其他行上的位移,即<strong>结束时间不同步</strong></li>
</ul>
<p>如果你想让结束时间同步,你必须解释如何同步;但是我看不到明显的方法。在</p>
<p>然后得到原始问题的以下解决方案(大写=事件,小写字母=位移,点=间隙,空格=“等待同步”,数字是<em>事件的开始时间</em>):</p>
<pre class="lang-none prettyprint-override"><code>0 123 4 567
AbC.D .e FG
A B.CcD EF
A BCD EfgHI
</code></pre>
<p>在以下示例中可以看到结束时间不同步:</p>
^{pr2}$
<p>还有一个更大的随机例子:</p>
<pre class="lang-none prettyprint-override"><code> 11 11 1 1 1 1 1 1 22 22 2 2 22 22 33 333 3 3 3 3 3 4 44444 4 4 4 45
01 2 34 5678 9 01 23 4 5 6 7 8 9 01 23 4 5 67 89 01 234 5 6 7 8 9 0 12345 6 7 8 90
AAAA BB CCC dd.. EEe Fff.. GGGGGg .... ... HHH .... IIii JJJ ... KKK LLLLl
abbbCCC DDDDDdd .. EEEEE Fff GGG HHH IIIii JJJjj KKKK LLLl Mno. PPP qR SSSSSs TT uuuVV
... AAAAA BBB CC DDDD ... EE FFFF GHhhIIII JJ. K Lll.m.... NNNO ....
...... AAAA .. .... BBB CCCCCc DDDDDd Ee FFFFff G hhhIIIII JJJ KLLLLLll M
.. AAA BBBCcc DD EE .. FFF gH IIIIIi J KKk LL MMMMM NNNNNn OOo PPQQQQ rrr...
AAAAa . BBBBbb CCCCC DDDDDd eeeFFFFF GG HH ..... IIIII JJ K LM.NNNNN .
AAAaaBBB CCCcc DDDDDdd EeFF ... GGgHHHH III JJJJ KKK llMMMm nnnOOOO PPPp ... Q
AAAAA BBBBB CCCC ..... DDD EEEEE FFFff .... GGGG HHHHhh II.... j . .
AAAaa.. BBBBbb CccDDDDD .... EEE .F GgghhhII Jj KKKK ... ... LLll ... MMMM N OooP
.... Aa ..BCCC ..... DDD EEEe FFf ..... GGGG HIIIIIii . JJ .... KKk LL
AAAAAa bbC..... DDDDD .... eeFFFFff GGGGG ... hh IIJJJ KKK L MMMMMmmNNNN
..aBBB CCCCc ..... ..... ... D. E FFFFFff ggHHhiiiJKKKk LLLLL mmmNNNOP Q RRR
AA BbCCCC DD Ee FFFFFff GGGGG HH IIIi JjjK.. LLLll MMMMmm .... . NNNOOOOOoo P
AB CCCCC ..... ddEEEE fffGgg HHHHHhh II jjKKKK LLLL MMMM nn.. OO PPPPPpp QQQQQqq
AAA BBB CCCC DDdd EE FFF gggHh IIIii JJJJ K LLLLl MMm NNOOOO . PP .QQQRRRRR
</code></pre>
<p>现在代码(抱歉,太长了,请看<code>Timetable.__init__</code>中有趣的部分,其余大部分都是打印出来的)。在</p>
<pre><code>from heapq import merge
from itertools import groupby, cycle, chain
from collections import defaultdict
from operator import attrgetter
from string import ascii_uppercase
# events are processed in this order:
# increasing start time, displacements (duration=0) first, and grouped by row_id
ev_sort_attrs = attrgetter("time", "duration", "row_id")
class Event:
def __init__(self, duration, displacement=0, visible=True, time=None, row_id=None):
self.duration = duration
self.displacement = displacement
self.visible = visible
self.time = time
self.row_id = row_id
self.pos = None
def draw(self, char):
return char * self.duration + char.lower() * self.displacement
def __lt__(self, other):
return ev_sort_attrs(self) < ev_sort_attrs(other)
def Gap(duration):
return Event(duration, visible=False)
class Timetable(list):
def __init__(self, *args):
""" compute positions for a list of rows of events """
list.__init__(self, *args)
# compute times for the events, and give them row_ids
for i, row in enumerate(self):
t = 0
for ev in row:
ev.time = t
t += ev.duration
ev.row_id = i
# map times to position for displacements and event
t2pos_disp = defaultdict(int) # maps times to position of synchronized start of displacements
t2pos_ev = defaultdict(int) # maps times to position of synchronized start of events and gaps
# the real work is done in the following loop
t_prev = 0
for t, g in groupby(merge(*self), key=attrgetter("time")):
# different times should have a minimum distance corresponding to their difference
t2pos_ev[t] = t2pos_disp[t] = max(t2pos_ev[t], t2pos_ev[t_prev] + t - t_prev)
t_prev = t
for (duration, row_id), g_row in groupby(g, key=attrgetter("duration", "row_id")): # process all displacements first, then the events
pos_ev = t2pos_ev[t] if duration > 0 else t2pos_disp[t] # events and displacements start at different
for ev in g_row:
ev.pos = pos_ev
pos_ev += ev.duration + ev.displacement
t2pos_ev[t + ev.duration] = max(t2pos_ev[t + ev.duration], pos_ev)
# keep our results...
self.t2pos_ev = t2pos_ev
self.t2pos_disp = t2pos_disp
@staticmethod
def str_row(row):
""" draw row, uppercase letters for real events, lower case letters for
displacements, dots for gaps"""
ev_chars = cycle(ascii_uppercase)
out = []
l = 0
for ev in row:
if ev.pos > l:
out.append(" " * (ev.pos - l))
out.append(ev.draw(next(ev_chars) if ev.visible else "."))
l = ev.pos + len(out[-1])
return "".join(out)
def __str__(self):
max_t, max_p = max(self.t2pos_ev.items())
w = len(str(max_t))
header_temp = [" " * w] * (max_p + 1)
for t, p in self.t2pos_ev.items():
header_temp[p] = "%*d" % (w, t)
headers = ("".join(header) for header in zip(*header_temp))
rows = (self.str_row(row) for row in self)
return "\n".join(chain(headers, rows))
if __name__ == "__main__":
# original example
row_one = [Event(1), Event(0,1), Event(1), Gap(1), Event(1), Gap(1), Event(0,1), Event(1), Event(1)]
row_two = [Event(1), Event(1), Gap(1), Event(1, 1), Event(1), Event(1), Event(1)]
row_thr = [Event(1), Event(1), Event(1), Event(1), Event(1), Event(0,1), Event(0,1), Event(1), Event(1)]
timetable = Timetable([row_one, row_two, row_thr])
print(timetable)
print("-" * 80)
# short example, shows ending times are not synchronized
print(Timetable([[Event(2, 1)], [Event(1, 1), Event(1)], [Event(1, 2), Event(1)]]))
print("-" * 80)
# larger random example
def random_row(l):
import random
res = []
t = 0
while t < l:
x = random.random()
if x < 0.1: res.append(Event(0, random.randint(1, 3)))
elif x < 0.8: res.append(Event(min(random.randint(1, 5), l - t), random.randint(0, 1) * random.randint(0, 2)))
else: res.append(Gap(min(random.randint(1, 5), l - t)))
t += res[-1].duration
return res
print(Timetable([random_row(50) for _ in range(15)]))
</code></pre>