patternMinor
Ordering elements so that some elements don't come between others
Viewed 0 times
comeelementsothersorderingbetweenthatsomedon
Problem
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(3)$.
-
$\pi = (1, 2, 4, 5, 3)$ is not a valid permutation, because $(1, 2, 3) \in S$ but $\pi(1)
-
$(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?
$$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(3)$.
-
$\pi = (1, 2, 4, 5, 3)$ is not a valid permutation, because $(1, 2, 3) \in S$ but $\pi(1)
-
$(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?
Solution
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 j \vee j>k$, relying on the fact that $i\neq j,j\neq k$.
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.
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.
Each constraint
$(\sigma_{m_i}, \sigma_{m_j}, \sigma_{m_k}) \in S \implies 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.
Context
StackExchange Computer Science Q#1255, answer score: 3
Revisions (0)
No revisions yet.