从小长度序列中找到序列

Question

我希望通过使用某些特定格式的事件来生成一个空间。让我在一个小例子中解释一下问题。

假设我有事件a、b、c、d、e、f。我将输入这些事件中的3个长度序列。从这些序列中，我想生成6个长度（事件数）的序列，并且序列中不会重复元素，即每个事件恰好使用一次。6个长度的序列需要满足一些规则。（在示例中解释）

例如：

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描述了在c之后d和e将出现，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生成这些序列的算法。目前我还没有任何代码，因为我尚未想到有效的算法。它需要非常高效地找到更长的序列。

如果问题不清楚，请让我知道。

谢谢

- genclik27

---

也许有向无环图（DAG）可以在那里发挥作用。 - Jakub M.

我以前没有使用过任何图算法，你能给我一些参考资料吗？ - genclik27

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']

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

- Jon Clements

---

抱歉回复晚了。它运行得非常好。我编辑了引发异常的部分，如果是无环的话就返回false。感谢您的答案。 - genclik27

Answer 2

你可以将模型构建为有向无环图。networkx python库将为您处理所有的图形操作。

要生成随机6元素序列，您可以枚举所有可能的序列，然后从中随机选择一个含有6个元素的序列。

以下是（糟糕但可行的）算法草图：

1. 从Jon的示例开始-构建图形并确保图形是DAG。 2. P是一个节点向量，在开始时为空。 3. 从图中选择一个随机节点，将该节点添加到P中。 4. 选择一个随机邻居节点。 5. 将新节点添加到P中。 6. 如果P具有所需长度（10或20或其他），则P是有效结果。 7. 否则，返回第4步。

- Jakub M.

---

正如我在问题中所说的，6个长度只是为了简单地解释问题。我将使用超过10个长度，甚至达到20个或更多。因此，枚举不是一个解决方案。 - genclik27

如果您不喜欢枚举所有可能性，可以遍历DAG并随机选择分支，输出满足长度要求的解决方案。 - Jakub M.

我该怎么做？你能给出类似的例子吗？ - genclik27

我会尝试。如果我能做到，它将会非常快速。之后我需要使用100长度。因此，拥有优化的算法非常重要。感谢您的回答。 - genclik27