python - 从小长度序列中查找序列

Question

我想通过使用特定格式的一些事件来生成一个空间。让我用一个小例子来解释这个问题。

假设我有事件 a、b、c、d、e、f。我将有 3 个长度的序列作为由这些事件组成的输入。从这些序列中，我想生成 6 个长度(事件数)的序列，并且序列中不会有重复的元素，即每个事件都将只使用一次。 6-length sequences需要满足一些规则。(例子说明)

例子:

Input: 
list1:['a','b','c']
list2:['c','d','e']
list3:['b','c','d']
list4:['a','c','g']
list5:['f','g','e'] 

List1描述的是，在6长序列中，b和c会在a之后，c会在b之后，即当顺序改变时，序列也会改变。 List2 以同样的方式描述了 d 和 e 将出现在 c 之后，e 将出现在 d 之后。将采用所有列表并记录规则。从这些序列中提取出所有规则后，我需要生成符合规则的 6 长序列。举个例子；

假设在我们的例子中(为简单起见)输入是 List1、List2 和 List3

Input: 
list1:['a','b','c']
list2:['c','d','e']
list3:['b','c','d']

然后这些列表的一些结果是；

['a','b','c','d','e']:它遵守从提取的这 3 个列表中提取的所有规则，比如 b 和 c 紧随其后a、d和e在c之后，c和d在b之后。 ©这里的重要说明，如果 c 需要在 a 之后，它们不需要在输出序列中相邻(6 长度)

不保证6长度的序列永远存在。首先，需要检查至少有一个这样的序列。如果不是，算法应该返回 false。举个例子;假设我们的输入是 Lis1、Lis2、Lis3、Lis4 和 Lis5。

Input: 
list1:['a','b','c']
list2:['c','d','e']
list3:['b','c','d']
list4:['a','c','g']
list5:['e','g','b'] 

a => b => c => g => b 这是不可能的，因为 b 不能跟在它自己之后。

我需要一种算法来在 Python 中生成这些序列。我现在没有任何代码，因为到目前为止我想不出任何有效的算法。它也需要非常有效地寻找更长的序列。

如果问题不清楚，请现在告诉我。

谢谢

Answer 1

这是一个起点:

import networkx as nx
from itertools import tee, izip

list1 = ['a','b','c']
list2 = ['c','d','e']
list3 = ['b','c','d']

g = nx.DiGraph()
for items in [list1, list2, list3]:
    a, b = tee(items)
    next(b)
    g.add_edges_from(izip(a, b))

print nx.topological_sort(g)
# ['a', 'b', 'c', 'd', 'e']

如果图形包含循环，这将引发异常...