查找与一组规则匹配的所有排列

我给出了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必须始终为1后

2之后，我尝试暴力破解，但它没”吨工作（虽然bruteforce应该在这里工作，N是在范围内（1,8）。）

任何想法？

2010-02-27 VaioIsBorn

你能解释一下N数是如何进入这个的吗？如果N的值在{1,2,3,4}，那么答案会是什么？ – 2010-02-27 00:44:27

从我所看到的情况来看，你给出的N个数字与你所问的问题无关。它是否正确？ – sykora 2010-02-27 00:44:34

N是有多少数字，在这种情况下N = 4，因为有四个数字，1..4。 – VaioIsBorn 2010-02-27 00:57:13

就像一个提示。

您可以将您的规则集作为图来处理。每个索引是一个顶点，每个规则是一个有向边。

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

P.S.在链接的维基百科页面上给出的第一个拓扑排序算法已经允许一个相当直接的解决方案，它将枚举所有有效的排列。这将需要一些努力和一些谨慎实施，但这不是火箭科学。

2010-02-27 00:44:59 AnT

作为进行完整拓扑排序之前的一步，您至少可以创建有序的片段来简化暴力破解。例如，如果优先级规则是： 3,4 4,5 5,8 你知道你可以置换[3458]与预规划，插入和您的整数的优先级规则不受约束的追加（本课程的概括进入上面） – 2010-02-27 01:31:09

暴力强制为going through every permutation，这是O（N！），并且对于每个置换简单地循环遍历每个规则以确认它们是aplpy，即O（M）。这结束了O（N！M），这有点荒谬，但它不应该对这样一个小集合“不起作用”。

2010-02-27 00:49:08 Tanzelax

实际上他可以检查规则，同时创建排列。这会大大减少时间，他最终会得出结果。 – Kugel 2010-02-27 00:55:25

我同意。如果N = 8是你需要能够处理的最高值，那么对于这样的事情来说，可能不值得花时间来提供比蛮力更好的东西。 – 2010-02-27 00:56:13

是的，对于暴力解决方案肯定有很多简单的优化，但是他提到他甚至遇到了问题。 – Tanzelax 2010-02-27 00:57:46

老实说，你最好的选择是回去，并获得蛮力解决方案的工作。一旦完成（如果你还有时间等），你可以寻找更好的算法。

编辑给羽绒选民。该学生是（应该）试图按时完成他的作业。通过它的声音，他的作业是一个编程练习，其中一个暴力解决方案就足够了。帮助他找出一个有效的算法并不能解决他的真正问题。

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

2010-02-27 01:14:03

@serial_downvoter：取消了你。哈哈！ – 2010-02-27 01:44:24

回答