rel-properties – Relation properties
Write a program that is able to list the following properties of binary relations:
- reflexive: ∀x, xRx
- irreflexive: ∀x, ¬xRx
- symmetric: ∀x,y, xRy ⊢ yRx
- antisymmetric: ∀x,y, xRy∧yRx ⊢ x=y
- asymmetric: ∀x,y, xRy ⊢ ¬yRx
- transitive: ∀x,y,z, xRy ∧ yRz ⊢ xRz
- equivalence: reflexive, symmetric and transitive
- order: reflexive, antisymmetric and transitive
- strict order: irreflexive, asymmetric and transitive
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
irreflexive
antisymmetric
asymmetric
transitive
strict order
reflexive
symmetric
antisymmetric
transitive
equivalence
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.
Scoring
- 1/6: works for the above example but produces output in an incorrect format
- 2/6: works for the above example and produces output in the correct format
- 5/6: works for other test cases
- 6/6: works for edge cases
Related exercises
try first: rel-member triangle
try also: rel-composition
try next: gcd
Copyright © 2020-2023 Rudy Matela
All rights reserved