[Solved]: Ordering elements so that some elements don’t come between others

ignougroup
Problem Detail: Given an integer $n$ and set of triplets of distinct integers $$S subseteq {(i, j, k) mid 1le 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 1 Suppose $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 2 If $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?

Asked By : Patrick87

Answered By : Dave Clarke

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 $ineq j,jneq k$.

  1. 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.
  2. 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)$.
  3. 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.
  4. 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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/1255  Ask a Question  Download Related Notes/Documents