Find permutation that satisfies conditions

Question

Suppose you what to find a permutation of integers {1, 2, ..., 13} that satisfy some rules.

Rules can be found in variable rules.

First of rules is {1, {2, 5}}. It means that 1 must come after 2 and 5 in the permutation (not necessary immediately after but some positions after).

Can you do the same as my code but with more concise and more easy to read code?

The solution may not be unique. Or there may exist no solution if rules are contradictory.

Clear[perm, rules, m]

perm = Range[13];
rules = {{1, {2, 5}}, {2, {3}}, {3, {7, 8}}, {4, {3}}, {5, {2, 
     9}}, {6, {7, 9, 11, 12}}, {7, {12, 13}}, {8, {7}}, {10, {9, 
     11}}, {11, {9}}, {12, {11}}, {13, {12}}};

While[Union[(If[
       Flatten[Position[perm, #[[1]]]][[1]] < (m = 
          Max[Flatten[(p |-> Position[perm, p]) /@ #[[2]]]]), 
       perm = (Insert[
            DeleteCases[#, 
             perm[[Flatten[Position[perm, #[[1]]]][[1]]]]], 
            perm[[Flatten[Position[perm, #[[1]]]][[1]]]], m] &@
          perm)]) & /@ rules] != {Null}]

perm

Clear[perm, rules, m]

---

{9, 11, 12, 13, 7, 8, 3, 2, 6, 5, 4, 10, 1}

Answer 1

One can use TopologicalSort for this.

edges[{s_, t_List}] := Thread[t -> s]
TopologicalSort[Graph[perm, Catenate[edges /@ rules]]]
(* {9, 11, 12, 13, 7, 8, 3, 4, 2, 5, 1, 6, 10} *)

The idea is to view for example {1, {2, 5}} as defining edges 2 -> 1, 5 -> 1. Then TopologicalSort gives the list of vertices of the graph in a order compatible with the edges: if u -> v appears, then u comes before v in the topological sort.