# Challenge description

• a relation is a set of ordered pairs of elements (in this challenge, we'll be using integers)

For instance, [(1, 2), (5, 1), (-9, 12), (0, 0), (3, 2)] is a relation.

• a relation is called transitive if for any two pairs of elements (a, b) and (b, c) in this relation, a pair (a, c) is also present,

• [(1, 2), (2, 4), (6, 5), (1, 4)] is transitive, because it contains (1, 2) and (2, 4), but (1, 4) as well,

• [(7, 8), (9, 10), (15, -5)] is transitive, because there aren't any two pairs (a, b), (c, d) present such that b = c.

• [(5, 9), (9, 54), (0, 0)] is not transitive, because it contains (5, 9) and (9, 54), but not (5, 54)

Given a list of pairs of integers, determine if a relation is transitive or not.

# Input / output

You will be given a list of pairs of integers in any reasonable format. Consider a relation

[(1, 6), (9, 1), (6, 5), (0, 0)]

The following formats are equivalent:

[(1, 6), (9, 1), (6, 5), (0, 0)] # list of pairs (2-tuples)
[1, 9, 6, 0], [6, 1, 5, 0] # two lists [x1, x2, ..., xn] [y1, y2, ..., yn]
[[1, 6], [9, 1], [6, 5], [0, 0] # two-dimentional int array
[4, 1, 6, 9, 1, 6, 5, 0, 0] # (n, x1, y1, ..., xn, yn)
[1+6i, 9+i, 6+5i, 0+0i] # list of complex numbers

... many others, whatever best suits golfing purposes


Output: a truthy value for a transitive relation, falsy otherwise. You may assume that the input will consist of at least one pair, and that the pairs are unique.

• Does the input have to be a list-like format, or can it be an adjacency--matrix-like format?
– xnor
Nov 21, 2016 at 21:25
• You should have a test case that is only transitive because the pairs are ordered. E.g. (1,3) (2,1) (3,4) (1,4) (2,4). If the pairs weren't ordered, this wouldn't be transitive because (2,3) is missing. Nov 21, 2016 at 21:26
• @MartinEnder I think you misinterpreted "ordered pairs". I don't think it means the pairs in an order - I think it means each pair has an order, first then second. Nov 22, 2016 at 1:09
• @isaacg that's what I meant. In other words, my test case is only truthy because the relation isn't implicitly symmetric. Nov 22, 2016 at 5:49
• Should the third test case ([(7, 8), (9, 10), (15, -5)]) be not transitive? Nov 22, 2016 at 14:08

f x=and[elem(a,d)x|(a,b)<-x,(c,d)<-x,b==c]


Usage example: f [(1,2), (2,4), (6,5), (1,4)]-> True.

(Outer)loop over all pairs (a,b) and (inner)loop over the same pairs, now called (c,d) and every time when b==c check if (a,d)is also an existent pair. Combine the results with logical and.

– Lynn
Nov 22, 2016 at 2:07
• @Lynn Check out the Prolog answer, then ;-) Nov 22, 2016 at 16:00

## Prolog, 66 bytes

t(L):-not((member((A,B),L),member((B,C),L),not(member((A,C),L)))).


The relation is not transitive if we can find (A,B) and (B,C) such that (A,C) doesn't hold.

# MATL, 27 25 bytes

7#u2e!l6MX>thl4\$XQttY*g<~


Input format is a matrix (using ; as row separator) where each pair of the relation is a column. For example, test cases

[(1, 2), (2, 4), (6, 5), (1, 4)]
[(7, 8), (9, 10), (15, -5)]
[(5, 9), (9, 54), (0, 0)]


are respectively input as

[1 2 6 1; 2 4 5 4]
[7 9 15; 8 10 -5]
[5 9 0; 9 54 0]


Truthy output is a matrix formed by ones. Falsy is a matrix that contains at least one zero.

Try it online!

### Explanation

The code first reduces the input integers to unique, 1-based integer values. From those values it generates the adjacency matrix; matrix-multiplies it by itself; and converts nonzero values in the result matrix to ones. Finally, it checks that no entry in the latter matrix exceeds that in the adjacency matrix.

## JavaScript (ES6), 69 67 bytes

a=>(g=f=>a.every(f))(([b,c])=>g(([d,e])=>c-d|!g(([d,c])=>b-d|c-e)))


Saved 2 bytes thanks to an idea by @Cyoce. There were four previous 69-byte formulations:

a=>a.every(([b,c])=>a.every(([d,e])=>c-d|a.some(([d,c])=>b==d&c==e)))
a=>!a.some(([b,c])=>!a.some(([d,e])=>c==d&a.every(([d,c])=>b-d|c-e)))
a=>a.every(([b,c])=>a.every(([d,e])=>c-d|!a.every(([d,c])=>b-d|c-e)))
(a,g=f=>a.every(f))=>g(([b,c])=>g(([d,e])=>c-d|!g(([d,c])=>b-d|c-e)))

• You might be able to shorten the second solution by making an abbreviation for .every Nov 21, 2016 at 23:53
• @Cyoce Indeed, you save 3 bytes each time by writing [e], so even though it costs 8 bytes to assign e you still save a byte. However, I went a step further by making an abbreviation for a.every, which saved a second byte.
– Neil
Nov 22, 2016 at 0:04

# Brachylog, 24 bytes

'{psc[A:B:B:C],?'e[A:C]}


Try it online!

Explanation:

'{psc[A:B:B:C],?'e[A:C]}
'{                     } it is impossible to find
c                    a flattened
s                     subset of
p                      a permutation of the input
[A:B:B:C]           that has four elements, with the second and third equal
,?         and such that the input
'e       does not contain
[A:C]  a list formed of the first and fourth element


In other words, if the input contains pairs [A:B] and [B:C], we can permute the input to put [A:B] and [B:C] at the start, delete all other elements, and produce a list [A:B:B:C]. Then we return truthy from the inner predicate (falsey from the whole program) if [A:C] isn't there.

## CJam (22 bytes)

{__Wf%m*{z~~=*}%\-e_!}


Online test suite. This is an anonymous block (function) which takes the elements as a two-level array, but the test suite does string manipulation to put the input into a suitable format first.

### Dissection

{         e# Begin a block
_       e#   Duplicate the argument
_Wf%    e#   Duplicate again and reverse each pair in this copy
m*      e#   Cartesian product
{       e#   Map over arrays of the form [[a b][d c]] where [a b] and [c d]
e#   are in the relation
z~~=* e#     b==c ? [a d] : []
}%
\-      e#   Remove those transitive pairs which were in the original relation
e_!     e#   Test that we're only left with empty arrays
}


# Pyth, 14 bytes

!-eMfqFhTCM*_M


Test suite

Input format is expected to be [[0, 0], [0, 1], ... ]

!-eMfqFhTCM*_M
!-eMfqFhTCM*_MQQQ    Variable introduction
_MQ      Reverse all of the pairs
*   Q     Cartesian product with all of the pairs
CM          Transpose. We now have [[A2, B1], [A1, B2]] for each pair
[A1, A2], [B1, B2] in the input.
f                Filter on
hT            The first element (the middle two values)
qF              Being equal
eM                 Take the end of all remaining elements (other two values)
-              Q    Remove the pairs that are in the input
!                    Negate. True if no transitive pairs were not in the input


## Mathematica, 49 bytes

#/.{x=___,{a_,b_},x,{b_,c_},x}/;#~FreeQ~{a,c}:>0&


Pure function which takes a list of pairs. If the input list contains {a,b} and {b,c} but not {a,c} for some a, b, c, replaces it with 0. Truthy is the input list, falsy is 0.

# C++14, 140 bytes

As unnamed lambda returning via reference parameter. Requires its input to be a container of pair<int,int>. Taking the boring O(n^3) approach.

[](auto m,int&r){r=1;for(auto a:m)for(auto b:m)if (a.second==b.first){int i=0;for(auto c:m)i+=a.first==c.first&&b.second==c.second;r*=i>0;}}


Ungolfed and usage:

#include<vector>
#include<iostream>

auto f=
[](auto m,int&r){
r=1;                         //set return flag to true
for(auto a:m)                //for each element
for(auto b:m)              //check with second element
if (a.second==b.first){  //do they chain?
int i=0;               //flag for local transitivity
for(auto c:m)          //search for a third element
i+=a.first==c.first&&b.second==c.second;
r*=i>0;                //multiply with flag>0, resulting in 0 forever if one was not found
}
}
;

int main(){
std::vector<std::pair<int,int>> m={
{1, 2}, {2, 4}, {6, 5}, {1, 4}
};

int r;
f(m,r);
std::cout << r << std::endl;

m.emplace_back(3,6);
f(m,r);
std::cout << r << std::endl;

m.emplace_back(3,5);
f(m,r);
std::cout << r << std::endl;

}


# Python 2, 9167 55 bytes

lambda s:all(b-c or(a,d)in s for a,b in s for c,d in s)


Try it online!

-24 bytes thanks to Leaky Nun
-12 bytes thanks to Bubbler

• 67 bytes (and fixed your code by changing lambda x to lambda s. Jun 23, 2017 at 18:29
• @LeakyNun Oh whoops, that was supid stupid of me. Thanks! Jun 23, 2017 at 18:36
• 55 bytes by unpacking at fors. Nov 6, 2018 at 4:28
• @Bubbler oh cool thanks Nov 6, 2018 at 8:07

Axiom 103 bytes

c(x)==(for i in x repeat for j in x repeat if i.2=j.1 and ~member?([i.1, j.2],x)then return false;true)


ungolfed:

c(x)==
for i in x repeat
for j in x repeat
if i.2=j.1 and ~member?([i.1, j.2],x) then return false
true

Type: Void


the exercises

(2) -> c([[1,2],[2,4],[6,5],[1,4]])
Compiling function c with type List List PositiveInteger -> Boolean
(2)  true
Type: Boolean
(3) -> c([[7,8],[9,10],[15,-5]])
Compiling function c with type List List Integer -> Boolean
(3)  true
Type: Boolean
(4) -> c([[5,9],[9,54],[0,0]])
Compiling function c with type List List NonNegativeInteger ->
Boolean
(4)  false


# Pyth - 22 21 bytes

.Am},hdedQfqFtPTsM^Q2


## Clojure, 56 53 bytes

Update: Instead of using :when I'll just check that for all pairs of [a b] [c d] either b != c or [a d] is found from the input set.

#(every? not(for[[a b]%[c d]%](=[b nil][c(%[a d])])))


Original:

Wow, Clojure for loops are cool :D This checks that the for loop does not generate a falsy value, which occurs if [a d] is not found from the input set.

#(not(some not(for[[a b]%[c d]% :when(= b c)](%[a d]))))


This input has to be a set of two-element vectors:

(f (set [[1, 2], [2, 4], [6, 5], [1, 4]]))
(f (set [[7, 8], [9, 10], [15, -5]]))
(f (set [[5, 9], [9, 54], [0, 0]]))


If input must be list-like then (%[a d]) has to be replaced by ((set %)[a d]) for extra 6 bytes.

Both these solutions are unnamed functions taking a list of ordered pairs as input and returning True or False.

# Mathematica, 65 bytes

SubsetQ[#,If[#2==#3,{#,#4},Nothing]&@@@Join@@@#~Permutations~{2}]&


#~Permutations~{2}] creates the list of all ordered pairs of ordered pairs from the input, and Join@@@ converts those to ordered quadruples. Those are then operated upon by the function If[#2==#3,{#,#4},Nothing]&@@@, which has a cool property: if the middle two elements are equal, it returns the ordered pair consisting of the first and last numbers; otherwise it returns Nothing, a special Mathematica token that automatically disappears from lists. So the result is the set of ordered pairs that needs to be in the input for it to be transitive; SubsetQ[#,...] detects that property.

# Mathematica, 70 bytes

And@@And@@@Table[Last@i!=#&@@j||#~MemberQ~{#&@@i,Last@j},{i,#},{j,#}]&


Table[...,{i,#},{j,#}] creates a 2D array indexed by i and j, which are taken directly from the input (hence are both ordered pairs). The function of those two indices is Last@i!=#&@@j||#~MemberQ~{#&@@i,Last@j}, which translates to "either the second element of i and the first element of j don't match, or else the input contains the ordered pair consisting of the first element of i and the last element of j". This creates a 2D array of booleans, which And@@And@@@ flattens into a single boolean.

# APL(NARS), 39 chars, 78 bytes

{∼∨/{(=/⍵[2 3])∧∼(⊂⍵[1 4])∊w}¨,⍵∘.,w←⍵}


test:

  f←{∼∨/{(=/⍵[2 3])∧∼(⊂⍵[1 4])∊w}¨,⍵∘.,w←⍵}
f (1 2) (2 4) (6 5) (1 4)
1
f (7 8) (9 10) (15 ¯5)
1
f (5 9) (9 54) (0 0)
0


one second 'solution' follow goto ways:

r←q w;i;j;t;v
r←1⋄i←0⋄k←↑⍴w⋄→3
r←0⋄→0
→0×⍳k<i+←1⋄t←i⊃w⋄j←0
→3×⍳k<j+←1⋄v←j⊃w⋄→4×⍳t[2]≠v[1]⋄→2×⍳∼(⊂t[1]v[2])∊w


## Common Lisp, 121 bytes

(lambda(x)(not(loop for(a b)in x thereis(loop for(c d)in x do(if(= b c)(return(not(member(,a ,d) x :test #'equal))))))))
`

Try it online!