Ordering elements so that some elements don't come between others
Here's a naive algorithm. It relies ultimately on brute force, but may perform okay sometimes. 

Each constraint
$(\sigma_{m_i}, \sigma_{m_j}, \sigma_{m_k}) \in S \implies i &lt; k \wedge \neg(i &lt; j &lt; k)$ consists of two conjuncts; let's call them type-$A$, $i &lt; k$, and type-$B$, $\neg(i &lt; j &lt; k)$. Each type-$B$ constraint can be equivalently written as a disjunction $i&gt;j \vee j&gt;k$, relying on the fact that $i\neq j,j\neq k$.


Collect all type-$A$ constraints. Call this $\Theta$. Check whether they are consistent, namely that this is a linearization of the ordering.  This takes $O(|S|)$-time in the number of constraints using topological sorting.
For each of the disjuncts in the type-$B$ constraint, check whether it is consistent with partial order $\Theta$. If it is not consistent, remove the disjunct. If both disjuncts are inconsistent with $\Theta$, then fail. Whenever just one type-$B$ constraint is removed, add the remaining one to $\Theta$. This step is $O(|S|^2)$.
Now there's an obvious algorithm for finding a solution, namely to consider all combinations of the type-$B$ disjunction pairs and test their consistency with $\Theta$, but this is clearly exponential in $|S|$.
One heuristic to improve performance  would be to treat the type-$B$ disjunction pairs as the branches of a tree---one pair forms the root, it's children are given by the second pair, their children by the third and so forth. Using this data structure, a solution is found by traversing the tree in a depth-first fashion. Each time a new constraint is added (using the label on a branch), consistency can be checked. Inconsistent subtrees can be pruned. 
If a leaf of the tree is reached, then we have a consistent set of constraints consisting of all of the type-$A$ constraints and one disjunct of the type-$B$ constraints. Linearise the result to obtain the desired ordering.


My preferred approach would actually be to encode it into a set of constraints and use a constraint solver such as Choco. I would introduce $n$ integer variables $x_i$ in the range $[0,n-1]$ and require that they were all distinct. Then I would encode each of the constraints above directly as constraints and then let Choco do it's business.