-1
$\begingroup$

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.

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

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.