# Possible orderings with constraints

Given variables {A, B, ,,,,,Z} We want to sort these varibles according to given constraints.

The constrains are in below format:

X Y Z

• meaning the third variable (Z) is not in the range between first and second variables (X, Y)
• X > Y or X > Y, we don't know. and Z can be greater than both X and Y or smaller than both which we don't know either
• for example XYZ, ZXY, YXZ, ZYX are all valid ordering given this constraint
• We are given at least 200 of such constraints such as:
A B C
E B K
X Y Z

....

We want to generate possible orderings of {A, B, ,,,,,Z} as many as possible Also the algorithm has to be faster than O(N!) (N is the number of variables)
I'm not sure how can I approach this problem, we don't have to generate all possible ordering but the more the better.

• What have you tried? Where did you get stuck? Where have you encounter this task? – Evil Nov 22 '17 at 3:44
• Can you credit the source where you encountered this problem? – D.W. Nov 22 '17 at 5:20

This may not directly answer your question, but can help. The problem you are looking at is complement to the Betweenness (https://en.wikipedia.org/wiki/Betweenness) problem. In your problem, for the constraint $X,Y,Z$ you do not want to generate sequences where-: 1. no sub-sequence beginning with X and ending with Y contains Z somewhere in between or 2. sub-sequence beginning with Y and ending with X contains Z somewhere in between. For the betweenness problem wit variables $X, Y, Z$ and constraint $X, Z, Y$ means $X, Z, Y$ and $Y, Z, X$ are the only valid solutions. So, one can look at efficient solution techniques for the betweenness problem and simply remove all those solutions to the betweenness problem from the $N!$ possible orderings.