4

Is there a shorter way to compute this boolean expression?

a < b < c || b < c < a || c < a < b

In JavaScript this would be:

a < b && b < c || b < c && c < a || c < a && a < b

Is there some useful maths or boolean algebra trick which would make this less cumbersome?

a, b and c are all numbers. In my particular use case, they are guaranteed to be distinct.

(For additional context, it arose in the process of answering this question)

Steve Bennett
  • 114,604
  • 39
  • 168
  • 219
  • Are `a`,`b`,`c` numbers? – adiga Jul 29 '21 at 09:47
  • 2
    I'd just do `isAscending(a, b, c) || isAscending(b, c, a) || isAscending(c, a, b)` where `isAscending = (a, b, c) => a < b && b < c`. – VLAZ Jul 29 '21 at 09:48
  • I think if they are numbers or other, this is not the question. What matters is that there is an order relationship – Lucas Bodin Jul 29 '21 at 09:49
  • `a < b && (b < c || c < a) || b < c && c < a` is shorter but less obvious ... sometimes the best code is not the shortest – Bravo Jul 29 '21 at 09:49
  • If all numbers are distinct, `((a < b) ^ (b < c) ^ (c < a)) === 0` is probably a start. – Sebastian Simon Jul 29 '21 at 09:49
  • 1
    I've only had two coffees so forgive me if this is dumb, but under what circumstances can this _not_ be true? Perhaps it's better to use those to test instead? – Martin Jul 29 '21 at 09:50
  • 1
    @Martin what if a = b = c :p – Bravo Jul 29 '21 at 09:50
  • 2
    @Martin `a = 3, b = 2, c = 1` would be false. – VLAZ Jul 29 '21 at 09:50
  • Thanks, sorry just to clarify what I meant was "_is this a situation where testing for the negative outcomes is easier than testing for the positive ones_"? – Martin Jul 29 '21 at 09:54
  • 1
    Added some more details. @Martin: No. The two situations are equally likely. – Steve Bennett Jul 29 '21 at 09:55
  • 1
    @Martin OP is testing if three variables are in ascending order. And doing three times by rotating them. The *opposite* would be if the values are in *descending* order or they are *equal*. That's *at least* the same amount of comparisons. – VLAZ Jul 29 '21 at 09:57
  • @SebastianSimon I *think* that works. Can you verify/prove and write it as an answer? – Steve Bennett Jul 29 '21 at 09:58
  • Yeah, I'm pretty convinced. The three expressions can't all be true. And the xor will return false if two of them are true, which is exactly what the original statement is testing. Can be shortened further to `!((a < b) ^ (b < c) ^ (c < a))` – Steve Bennett Jul 29 '21 at 09:59
  • Or even (without having to worry about whether bitwise xor is the same as boolean xor): (a < b) + (b < c) + (c < a) === 2 – Steve Bennett Jul 29 '21 at 10:03
  • @VLAZ It's not though is it, because if `(a >= b || b >= c)` then that would solve that case, which is many less operations than the original equation – Martin Jul 29 '21 at 10:03
  • @SteveBennett are these going to have a constant ratio to them? e.g, `1`, `2`, 3`, or `2`, `4`, `6` or similar? If so, you'd also be able to drop them to a common base, e.g., `-1`, `0`, and `1` then check check them against a precomputed table of results. – VLAZ Jul 29 '21 at 10:05
  • @Martin if `a > b` then `b < c < a` might still be valid. E.g. `a = 3, b = 1, c = 2` – VLAZ Jul 29 '21 at 10:06
  • No, no assumptions like that - other than they are (in this case) all in the range -PI...PI – Steve Bennett Jul 29 '21 at 10:07
  • @VLAZ In which case it simply becomes `!(a >= b && b >= c && c >= a)`. Although `b < c < a` couldn't be true anyway if `b >= c` so it becomes superfluous – Martin Jul 29 '21 at 10:07
  • @Martin [no, it doesn't work](https://jsbin.com/cobunuh/edit?js,console). – VLAZ Jul 29 '21 at 10:12

1 Answers1

4

You have 3 different boolean comparisons out of which you want 2 to hold. (Strictly, 2 or more, but in your case you can never have all 3). So you can write

a < b && b < c || b < c && c < a || c < a && a < b

as

(a < b) + (b < c) + (c < a) == 2
Bergi
  • 630,263
  • 148
  • 957
  • 1,375