index | submit | rank | book

rel-properties – Relation properties

Write a program that is able to list the following properties of binary relations:

Relation properties

In this exercise, by convention, we deal with relations over the finite set of natural numbers from 0 to n-1.

Input and output

Input will consist of several relations declared either as a matrix or as a set of ordered pairs.

Each matrix declaration begins with a line containing the word matrix and number n indicating the size of the domain and co-domain. This is followed by n lines with a matrix representation. Input is given so that 1 ≤ n ≤ 30.

Each list declaration begins with a line containing the word list and number n. This is followed by zero or more lines with the ordered pairs of the relation followed by a line containing a dash -.

For each relation given in the input output should contain a list of properties found in the given relation followed by a blank line.

Example Input

matrix 3
0 1 1
0 0 1
0 0 0
list 4
0 0
1 1
2 2
3 3

Example Output

strict order


For the purposes of this exercise, you should focus on correctness and not on performance or optimal complexity. Solutions in O(n³), O(n³ log n) or O(n⁵) should be enough to fall within the time limit.


try first: rel-member triangle

try also: rel-composition

try next: gcd

index | submit | rank | book

Copyright © 2020-2021 Rudy Matela
All rights reserved