Given an integer $n$ and set of triplets of distinct integers$$S \subseteq \{(i, j, k) \mid 1\le i,j,k \le n, i \neq j, j \neq k, i \neq k\},$$find an algorithm which either finds a permutation $\pi$ of the set $\{1, 2, \dots, n\}$ such that$$(i,j,k) \in S \implies (\pi(j)<\pi(i)<\pi(k)) ~\lor~ (\pi(i)<\pi(k)<\pi(j))$$or correctly determines that no such permutation exists.  Less formally, we want to reorder the numbers 1 through $n$; each triple $(i,j,k)$ in $S$ indicates that $i$ must appear before $k$ in the new order, but $j$ must not appear between $i$ and $k$.Example 1Suppose $n=5$ and $S = \{(1,2,3), (2,3,4)\}$.  Then$\pi = (5, 4, 3, 2, 1)$ is not a valid permutation, because $(1, 2, 3)\in S$, but $\pi(1) > \pi(3)$.$\pi = (1, 2, 4, 5, 3)$ is not a valid permutation, because $(1, 2, 3) \in S$ but $\pi(1) < \pi(3) < \pi(5)$.$(2, 4, 1, 3, 5)$ is a valid permutation.Example 2If $n=5$ and $S = \{(1, 2, 3), (2, 1, 3)\}$, there is no valid permutation.  Similarly, there is no valid permutation if $n=5$ and $S = \{(1,2,3), (3,4,5), (2,5,3), (2,1,4)\}$  (I think; may have made a mistake here).Bonus: What properties of $S$ determine whether a feasible solution exists?
Ordering elements so that some elements don't come between others
algorithms;optimization;scheduling
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 < k \wedge \neg(i < j < k)$ consists of two conjuncts; let's call them type-$A$, $i < k$, and type-$B$, $\neg(i < j < k)$. Each type-$B$ constraint can be equivalently written as a disjunction $i>j \vee j>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.