3

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

假设我有事件 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描述了b和c在a之后，c在6长序列中在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 中生成这些序列。我现在没有任何代码，因为到目前为止我想不出任何有效的算法。它也需要非常有效地找到更长的序列。

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

谢谢

4

2 回答 2

3

这是一个起点：

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

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

于 2013-08-25T14:02:14.173 回答
1

您可以将模型构建为有向无环图。networkx python 库将为您处理所有图形内容。

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

（糟糕但有效）算法的草图：

  1. 从 Jon 的示例开始 - 构建图并确保该图是 DAG
  2. P是节点向量，开头为空
  3. 从图中随机选择一个节点，将该节点添加到 P
  4. 选择一个随机邻居节点
  5. 将新节点添加到 P
  6. 如果 P 具有所需的长度（10 或 20 或其他），则 P 是有效结果。
  7. 否则，转至 4
于 2013-08-25T14:03:17.947 回答