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

Question

我得到了 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)内。)

有什么想法吗？

Answer 1

作为提示。

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

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

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