0

我有 n 个事件 {v1, ..., vn} 将在某些特定时间 {t1, ..., tk} 发生，其中 k <= n （多个事件可以同时发生），我需要列出这可能发生的每一种方式。

例如，如果我们有 2 个事件，我可以有：

{v1 < v2}，{v2 < v1}（2 次）

{v1 = v2}（1 次）

如果我们有 3 个事件，我可以有 3 个不同时间的所有 6 个订单，加上

{v1 = v2 < v3}、{v1 = v3 < v2}、{v2 = v3 < v1}、{v1 < v2 = v3}、{v2 < v1 = v3}、{v3 < v1 = v2}（2 次)

{v1 = v2 = v3}（1 次）

所以我实际上并不想要所有可能的分组，因为例如 {v1 = v2 < v3} 等价于 {v2 = v1 < v3}。

我的想法是，我需要为 k=n 的情况生成 n 个事件的所有排列，我有一个方法要做，所以也许我可以在此之上生成可能的类别，然后修剪掉重复，但我不确定如何检查，例如，{v3 = v4 = v2 < v1 = v6 < v5} 是否与我们之前有效接受的内容重复。

从排列列表中操作并找出如何删除重复项而不重新检查我们迄今为止存档的列表时，也许可以更加系统化？

我意识到即使对于中等数量的事件，这也不会在合理的时间内起作用，但我想把它推得尽可能高，6 就可以了，8 或 10 甚至更好。

我正在使用 MATLAB，但我愿意使用任何人可能建议作为此类问题的最佳语言的任何语言，并且非常欢迎和赞赏任何关于通用语言不可知方法的建议。

4

1 回答 1

1

这是一种方法（代码如下）：

生成使用任何标准算法的排列（显然有 n! 个排列）。对于每个排列，枚举所有可能的公式：v1…vnvp1…vpn

vp1 R1 vp2 R2 vp3 … Rn-1 vpn

where总是可以，也可以是if 。Ri<=pi < pi+1

例如，如果 n 为 3：

v1 v2 v3: v1 < v2 < v3; v1 < v2 = v3; v1 = v2 < v3; v1 = v2 = v3
v1 v3 v2: v1 < v3 < v2; v1 = v3 < v2
v2 v1 v3: v2 < v1 < v3; v2 < v1 = v3
v2 v3 v1: v2 < v3 < v1; v2 = v3 < v1
v3 v1 v2: v3 < v1 < v2; v3 < v1 = v2
v3 v2 v1: v3 < v2 < v1

您可以递归地枚举关系（这实际上是我在上面手动操作的方式）。

编辑：这是 Sloane 序列A000670，链接包含各种可能有用的参考。对于 n=9，计数为 7087261，这似乎非常实用；对于 n=10，它是 102247563，这很容易在现代桌面计算的范围内。（不过我不知道matlab）。

这是一个python实现：

def rels(perm):
  if len(perm) == 1:
    yield perm
  else:
    for p in rels(perm[1:]):
      yield (perm[0], '<') + p
      if perm[0] < perm[1]:
        yield (perm[0], '=') + p

def orders(n):
  return reduce(lambda a,b:a+b,
                [[i for i in rels(p)] for p in itertools.permutations(range(n))])

>>> print '\n'.join(map(repr,[o for o in orders(4)]))
(0, '<', 1, '<', 2, '<', 3)
(0, '=', 1, '<', 2, '<', 3)
(0, '<', 1, '=', 2, '<', 3)
(0, '=', 1, '=', 2, '<', 3)
(0, '<', 1, '<', 2, '=', 3)
(0, '=', 1, '<', 2, '=', 3)
(0, '<', 1, '=', 2, '=', 3)
(0, '=', 1, '=', 2, '=', 3)
(0, '<', 1, '<', 3, '<', 2)
(0, '=', 1, '<', 3, '<', 2)
(0, '<', 1, '=', 3, '<', 2)
(0, '=', 1, '=', 3, '<', 2)
(0, '<', 2, '<', 1, '<', 3)
(0, '=', 2, '<', 1, '<', 3)
(0, '<', 2, '<', 1, '=', 3)
(0, '=', 2, '<', 1, '=', 3)
(0, '<', 2, '<', 3, '<', 1)
(0, '=', 2, '<', 3, '<', 1)
(0, '<', 2, '=', 3, '<', 1)
(0, '=', 2, '=', 3, '<', 1)
(0, '<', 3, '<', 1, '<', 2)
(0, '=', 3, '<', 1, '<', 2)
(0, '<', 3, '<', 1, '=', 2)
(0, '=', 3, '<', 1, '=', 2)
(0, '<', 3, '<', 2, '<', 1)
(0, '=', 3, '<', 2, '<', 1)
(1, '<', 0, '<', 2, '<', 3)
(1, '<', 0, '=', 2, '<', 3)
(1, '<', 0, '<', 2, '=', 3)
(1, '<', 0, '=', 2, '=', 3)
(1, '<', 0, '<', 3, '<', 2)
(1, '<', 0, '=', 3, '<', 2)
(1, '<', 2, '<', 0, '<', 3)
(1, '=', 2, '<', 0, '<', 3)
(1, '<', 2, '<', 0, '=', 3)
(1, '=', 2, '<', 0, '=', 3)
(1, '<', 2, '<', 3, '<', 0)
(1, '=', 2, '<', 3, '<', 0)
(1, '<', 2, '=', 3, '<', 0)
(1, '=', 2, '=', 3, '<', 0)
(1, '<', 3, '<', 0, '<', 2)
(1, '=', 3, '<', 0, '<', 2)
(1, '<', 3, '<', 0, '=', 2)
(1, '=', 3, '<', 0, '=', 2)
(1, '<', 3, '<', 2, '<', 0)
(1, '=', 3, '<', 2, '<', 0)
(2, '<', 0, '<', 1, '<', 3)
(2, '<', 0, '=', 1, '<', 3)
(2, '<', 0, '<', 1, '=', 3)
(2, '<', 0, '=', 1, '=', 3)
(2, '<', 0, '<', 3, '<', 1)
(2, '<', 0, '=', 3, '<', 1)
(2, '<', 1, '<', 0, '<', 3)
(2, '<', 1, '<', 0, '=', 3)
(2, '<', 1, '<', 3, '<', 0)
(2, '<', 1, '=', 3, '<', 0)
(2, '<', 3, '<', 0, '<', 1)
(2, '=', 3, '<', 0, '<', 1)
(2, '<', 3, '<', 0, '=', 1)
(2, '=', 3, '<', 0, '=', 1)
(2, '<', 3, '<', 1, '<', 0)
(2, '=', 3, '<', 1, '<', 0)
(3, '<', 0, '<', 1, '<', 2)
(3, '<', 0, '=', 1, '<', 2)
(3, '<', 0, '<', 1, '=', 2)
(3, '<', 0, '=', 1, '=', 2)
(3, '<', 0, '<', 2, '<', 1)
(3, '<', 0, '=', 2, '<', 1)
(3, '<', 1, '<', 0, '<', 2)
(3, '<', 1, '<', 0, '=', 2)
(3, '<', 1, '<', 2, '<', 0)
(3, '<', 1, '=', 2, '<', 0)
(3, '<', 2, '<', 0, '<', 1)
(3, '<', 2, '<', 0, '=', 1)
(3, '<', 2, '<', 1, '<', 0)
于 2013-09-22T02:58:35.410 回答