Now this problem is very similar to the consecutive 1's problem. The consecutive 1's problem is solved by using the PQ-tree. Recall the algorithm: given a set \(\Omega = \lbrace s_1, \dots , s_m\rbrace \)  and a set of subsets of \(\Omega \) , say, \(S_1, \dots , S_m\) , the algorithm outputs a PQ tree \(T\)  with leaves \(\lbrace s_1, \dots , s_m\rbrace \)  and the property that \(PQ(T)\)  is the set of all orderings of \(\Omega \)  where for all \(S_i\)  (\(1\le i \le m\) ), the elements in \(S_i\)  are contiguous. The algorithm has \(m\)  iterations. The algorithms starts will a trivial PQ tree \(T\)  and at the end of the \(k\) -th iteration the PQ tree \(T\)  has the property that \(PQ(T)\)  is the set of all orderings of \(\Omega \)  where for all \(S_i\)  (\(1\le i \le k-1\) ), the elements in \(S_i\)  are contiguous in the ordering. At iteration \(k\) , the PQ tree \(T\)  is updated using the algorithm \(Restrict(T,S_k)\)[1]}In [1]} they define the update algorithm as \(Reduce(T,S)\) . In this paper we use the name \(Restrict(T,S)\)  instead of \(Reduce(T,S)\)  as we think that the word “Restrict" is more suitable.. If for some \(S_k\) , \(Restrict(T,S_k)\)  cannot be performed, the algorithm halts and rejects.
