Given a set $S$ and a partial order $\prec$ over $S$, I'm looking for a way to "efficiently" generate a list of linear extensions of $\prec$.  Suppose the partial order is given by a `List` of pairs $\{x,y\}$ such that $x,y\in S$.  For example, if $S = \{a,b,c\}$, then $\{\{a,c\},\{b,c\}\}$ defines a partial order where $a \prec c$ and $b \prec c$.

Essentially, given a list $S$ and a list of pairs $P$, I want to generate a list of permutations which respect the orders of the pairs in $P$.

    linearExtensions[{a, b, c, d, e}, {{a, b}, {c, b}, {c, d}, {e, d}}]
    (* {{a, c, b, e, d}, {a, c, e, b, d}, {a, c, e, d, b}, {a, e, c, b, d},
        {a, e, c, d, b}, {c, a, b, e, d}, {c, a, e, b, d}, {c, a, e, d, b},
        {c, e, a, b, d}, {c, e, a, d, b}, {c, e, d, a, b}, {e, a, c, b, d},
        {e, a, c, d, b}, {e, c, a, b, d}, {e, c, a, d, b}, {e, c, d, a, b}} *)

Since $\{a,b\}$ is in $P$, the permutation $\{b, c, a, d, e\}$ is not a linear extension because $b$ comes before $a$.

I've written two different functions which do the job, both using pattern matching, but I've been using Mathematica for less than a week and am still getting into the functional mindset.  I'm interested to see how seasoned Mathematica users would tackle this problem.

My first approach was to use `NestWhile`:

    linearExtensions[set_, po_] := 
        Module[{patterns},
            patterns = {___, #[[1]], ___, #[[2]], ___}& /@ po;
            First[NestWhile[{Cases[#[[1]], First[#[[2]]]], 
                Rest[#[[2]]]} &, {Permutations[set], patterns}, Length[#[[2]]] > 0&]]
        ]

My second approach, which turned out to be significantly slower, was to expand a set of rules from the partial order and use select on the list of permutations.

    linearExtensions[set_, po_] :=
        Module[{poQ},
            poQ[rule_] := And @@ (MatchQ[rule, {___, #[[1]], ___, #[[2]], ___}]& /@ po);
            Select[Permutations[set], poQ[#]&]
        ]

Note that on a list of length $n$ there can be $\Omega(n!)$ linear extensions, so by "efficient," I don't mean polynomial-time.