import itertools,math
from collections import defaultdict
def collapse(path):
    result=[];previous=object()
    for token in path:
        if token is not None and not isinstance(token,str):
            raise ValueError('string tokens or None blank required')
        if token!=previous and token is not None:result.append(token)
        previous=token
    return tuple(result)
assert collapse(['ا','ا',None,'ا'])==('ا','ا')
assert collapse(['ا','ا'])==('ا',)
assert collapse([None,None])==()
assert collapse([])==()
# Two independent time-step distributions, conditional on a toy fixed input.
frames=[{None:.6,'ا':.4},{None:.6,'ا':.4}]
scores=defaultdict(float)
for path in itertools.product(*[tuple(f) for f in frames]):
    prob=math.prod(frames[t][token] for t,token in enumerate(path))
    scores[collapse(path)]+=prob
best_path=tuple(max(f,key=f.get) for f in frames)
print('greedy path',best_path,'greedy output',collapse(best_path))
print('summed sequence probabilities',dict(scores))
assert collapse(best_path)==()
assert abs(scores[('ا',)]-.64)<1e-12
assert abs(scores[()]-.36)<1e-12
assert max(scores,key=scores.get)==('ا',)
assert abs(sum(scores.values())-1)<1e-12