Challenge description

Let's start with some definitions:

  • 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.

  • \$\begingroup\$ Does the input have to be a list-like format, or can it be an adjacency--matrix-like format? \$\endgroup\$
    – xnor
    Nov 21, 2016 at 21:25
  • \$\begingroup\$ 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. \$\endgroup\$ Nov 21, 2016 at 21:26
  • 1
    \$\begingroup\$ @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. \$\endgroup\$
    – isaacg
    Nov 22, 2016 at 1:09
  • \$\begingroup\$ @isaacg that's what I meant. In other words, my test case is only truthy because the relation isn't implicitly symmetric. \$\endgroup\$ Nov 22, 2016 at 5:49
  • \$\begingroup\$ Should the third test case ([(7, 8), (9, 10), (15, -5)]) be not transitive? \$\endgroup\$
    – wnnmaw
    Nov 22, 2016 at 14:08

17 Answers 17


Haskell, 42 bytes

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.

  • \$\begingroup\$ Most readable answer so far! \$\endgroup\$
    – lynn
    Nov 22, 2016 at 2:07
  • \$\begingroup\$ @Lynn Check out the Prolog answer, then ;-) \$\endgroup\$
    – coredump
    Nov 22, 2016 at 16:00

 Prolog, 66 bytes


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


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!


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


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

  • 1
    \$\begingroup\$ You might be able to shorten the second solution by making an abbreviation for .every \$\endgroup\$
    – Cyoce
    Nov 21, 2016 at 23:53
  • \$\begingroup\$ @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. \$\endgroup\$
    – Neil
    Nov 22, 2016 at 0:04

Pyth, 14 bytes


Test suite

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

!-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

Brachylog, 24 bytes


Try it online!


'{                     } 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)


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.


{         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

Mathematica, 49 bytes


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:


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
        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;
 std::cout << r << std::endl;
 std::cout << r << std::endl;
 std::cout << r << std::endl;


Python 2, 91 67 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

  • \$\begingroup\$ 67 bytes (and fixed your code by changing lambda x to lambda s. \$\endgroup\$
    – Leaky Nun
    Jun 23, 2017 at 18:29
  • \$\begingroup\$ @LeakyNun Oh whoops, that was supid stupid of me. Thanks! \$\endgroup\$
    – hyper-neutrino
    Jun 23, 2017 at 18:36
  • \$\begingroup\$ 55 bytes by unpacking at fors. \$\endgroup\$
    – Bubbler
    Nov 6, 2018 at 4:28

05AB1E, 14 bytes


Port of @isaacg's Pyth answer, so make sure to upvote him/her as well!
Also takes the input as a list of pairs (e.g. [[1,2],[3,4],...]).

Try it online or verify all test cases.


í           # Reverse each pair of the (implicit) input-list
 â          # Get the cartesian product of this list and the (implicit) input-list,
            # creating pairs of pairs
  €         # Map over each pair of pairs:
   ø        #  Zip/transpose; swapping rows/columns
            # (we now have a list of [[x1,y2],[y1,x2]] of each pair in the input-list, 
            # including those where [x1,y1]==[x2,y2])
    ʒ       # Filter this list of 2x2 blocks by:
     θ      #  Get the last row: [y1,x2]
      Ë     #  Check if the values in the pair are the same: y1==x2
    }€      # After the filter: map over each remaining 2x2 block:
      н     #  Leave just the first row: [x1,y2]
       IK   # Remove all input-pairs from this list of remaining pairs
         g  # And then check if the length
          _ # is equal to 0 (1 if the list was empty; 0 if not)
            # (after which the result is output implicitly)

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)


  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

                                                                   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 ->
   (4)  false

Pyth - 22 21 bytes


Test Suite.


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])])))


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


#~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


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←⍵}


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

one second 'solution' follow goto ways:

r←q w;i;j;t;v

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!


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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