11

我得到 N 个数字，并为他们应用 M 条关于他们的订单的规则。规则以一对索引表示，每一对 (A, B) 都告诉索引 A 的数字（第 A 号）必须在第 B 号之后 - 它不必在他旁边.

Ex: N = 4
    1 2 3 4
    M = 2
    3 2
    3 1

Output: 1234, 4213, 4123, 2134, 2143, 2413, 1423 ...Maybe there are even more:)

该算法应该给我所有不违反规则的可用排列，就像在示例中一样 - 3 必须始终在 2 和 1 之后。

我尝试了暴力破解，但它没有用（虽然暴力破解应该在这里工作，N 在范围（1,8）内。）

有任何想法吗 ？

4

3 回答 3

9

只是作为一个提示。

您可以将您的规则集视为图表。每个索引是一个顶点，每个规则是一个有向边。

数字的任何正确排序（即满足规则的排列）对应于上图的所谓拓扑排序。为了生成数字的所有有效排序，您需要生成该图的所有可能的拓扑排序。

PS 在链接的 Wikipedia 页面上给出的第一个拓扑排序算法已经允许一个相当简单的解决方案，它可以枚举所有有效的排列。实施需要付出一些努力和谨慎，但这不是火箭科学。

于 2010-02-27T00:44:59.933 回答
4

蛮力将经历每个排列，即 O(N!)，并且对于每个排列，只需循环遍历每个规则以确认它们是否适用，即 O(M)。这最终得到了 O(N!M) ，这有点荒谬，但对于这么小的集合来说，它不应该“不起作用”。

于 2010-02-27T00:49:08.553 回答
1

老实说，您最好的选择是返回并使用蛮力解决方案。完成后（如果您还有时间等），您可以寻找更好的算法。

编辑反对票。学生正在（应该）努力按时完成作业。听上去，他的作业是一个编程练习，其中一个蛮力解决方案就足够了。帮助他找出一个有效的算法并不能解决他真正的问题。

在这种情况下，他尝试了简单的蛮力方法（每个人都同意应该为小N值工作）并过早地放弃它，尝试一些可能更困难的东西。任何有经验的开发人员都会告诉你这是一个坏主意。学生需要并且应该被告知，如果他是明智的，他会注意的。但显然，这是他的选择……

于 2010-02-27T01:14:03.843 回答