Uma matriz P(n times n) de valores int é uma matriz de permutação se em cada linha e em cada coluna de P houver n-1 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 P de tamanho ntimes n 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 P sejam 0 ou 1. Se aparecer outro valor, já podemos descartar.
Para cada linha i de P, somamos todos os elementos P[i][j] para j=0 até n-1. Se a soma for diferente de 1, não é matriz de permutação.
De forma análoga, para cada coluna j de P, somamos todos os elementos P[i][j] para i=0 até n-1. Se a soma for diferente de 1, não é matriz de permutação.

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 P é 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 O(n^2) e retorna verdadeiro se P for matriz de permutação e falso caso contrário.

Exercícios relacionados