Return to Question

My first approach was to use NestWhile:

My first approach was to use NestWhile (edit: this is ugly! I did not know about the Fold[] function when I wrote this):

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[{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.