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

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

就像一个提示.

您可以将您的规则集视为图形.每个索引都是一个顶点,每个规则都是一个有向边.

数字的任何适当排序(即满足规则的排列)对应于上述图的所谓拓扑排序.为了生成数字的所有有效排序,您需要生成该图的所有可能的拓扑排序.

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