Uma matriz
de valores int é uma matriz de permutação se em cada linha e em cada coluna de P houver
elementos nulos e um único elemento igual a 1 . Escrever um programa que, dada uma matriz P, verifica se P é matriz de permutação.
Passo 1
O enunciado pede um método que receba uma matriz inteira
de tamanho
e verifique se ela é uma matriz de permutação, ou seja, se em cada linha e em cada coluna há exatamente um elemento igual a 1 e todos os outros iguais a 0.
Passo 2
Antes de mais nada precisamos garantir que todos os elementos de
sejam 0 ou 1. Se aparecer outro valor, já podemos descartar.
Para cada linha de
, somamos todos os elementos
para
até
. Se a soma for diferente de 1, não é matriz de permutação.
De forma análoga, para cada coluna de
, somamos todos os elementos
para
até
. Se a soma for diferente de 1, não é matriz de permutação.
Para cada linha
De forma análoga, para cada coluna
Passo 3
Se todas as linhas e colunas satisfizerem soma igual a 1 e não houver valores diferentes de 0 ou 1, então
é de fato uma matriz de permutação.
Resposta
A seguir um pseudocódigo que implementa a verificação:
fun isPermutationMatrix(P, n):
// Verifica valores válidos e soma das linhas
for i = 0 to n-1:
rowSum = 0
for j = 0 to n-1:
if P[i][j] != 0 and P[i][j] != 1:
return false
rowSum = rowSum + P[i][j]
if rowSum != 1:
return false
// Verifica soma das colunas
for j = 0 to n-1:
colSum = 0
for i = 0 to n-1:
colSum = colSum + P[i][j]
if colSum != 1:
return false
return true
Esse algoritmo roda em tempo
e retorna verdadeiro se
for matriz de permutação e falso caso contrário.