algorithm - 列出 n 个元素的排序到 k 个类别

Question

我有 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，但我愿意使用任何人建议的任何语言来解决此类问题，并且非常欢迎和赞赏任何关于通用语言不可知论方法的建议。

Answer 1

这是一种方法(代码如下):

生成 v<sub>1</sub>…v<sub>n</sub> 的排列使用任何标准算法(显然有 n!排列)。对于每个排列 v<sub>p<sub>1</sub></sub>…v<sub>p<sub>n</sub></sub>枚举所有可能的公式:

v<sub>p<sub>1</sub></sub> R<sub>1</sub> v<sub>p<sub>2</sub></sub> R<sub>2</sub> v<sub>p<sub>3</sub></sub> … R<sub>n-1</sub> v<sub>p<sub>n</sub></sub>

哪里R<sub>i</sub>永远可以是<也可以是 =如果p<sub>i</sub> < p<sub>i+1</sub> .

例如，如果 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

您可以递归地枚举关系(这实际上是我在上面手动完成的方式)。

编辑:这是斯隆序列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)