rel-composition – Relation composition
Write a program that is able to compose binary relations. Given relation R and relation S, it should compute relation RS, in other words, “R;S”, “R before S”, “S∘R” or “S after R”.
Input and output
Input begins with a number n indicating the size of domain and codomain. Followed by 2n lines with two matrix representations of relations R and S. The same repeats again. For each pair of relations R and S given in the input, your program should produce a matrix representation of the resulting RS relation.
Example input
3
0 1 1
0 0 1
0 0 0
0 0 0
1 0 0
1 1 0
4
1 1 1 1
0 1 0 0
0 0 1 0
1 1 1 1
1 0 0 1
1 1 0 1
1 0 1 1
1 0 0 1
Example output
1 1 0
1 1 0
0 0 0
1 1 1 1
1 1 0 1
1 0 1 1
1 1 1 1
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
try also: rel-properties
try next: gcd
Copyright © 2020-2024 Rudy Matela
This text is available under the CC BY-SA 4.0 license.
Originally available on cscx.org/rel-composition