index | submit | rank | book

rel-mtol – Relation, matrix to list

Write a program that converts between representations of binary relations: from a matrix representation to a set-of-ordered-pairs representation.

Relation, matrix to list

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 contain several relations R represented as a matrix. Each representation begins with a line containing a number n followed n lines each containing the matrix representation with 1 for related and 0 for not related. The number n represents the size of the domain and co-domain.

For each relation given in the input, output should contain a representation as a set-of-ordered pairs. The first line should be n, the size of the domain and co-domain. Then there should be a line for each ordered pair in increasing order followed by a blank line.

Example input

3
0 1 1
0 0 1
0 0 0
4
0 0 0 0
0 1 0 0
0 0 1 0
0 0 0 0

Example output

3
0 1
0 2
1 2

4
1 1
2 2

Scoring

try first: set-member

try also: rel-ltom

try next: rel-member

index | submit | rank | book

Copyright © 2020-2021 Rudy Matela
All rights reserved