Primeira vez aqui? Seja bem vindo e cheque o FAQ!
x

Como criar uma matriz transposta?

0 votos
54 visitas
perguntada Set 23 em Ciência da Computação por Alan Antunes Rosendo (26 pontos)  
editado Set 23 por Alan Antunes Rosendo

Você tem uma fita magnética com um milhão de palavras, representando os elementos em uma matriz 1000x1000 guardada em ordem por linhas: \(a_{1,1}a_{1,2}...a_{1,1000}a_{2,1}...a_{2,1000}...a_{1000,1000}\). Como criar uma fita em que cada elemento é guardado pelas colunas: \(a_{1,1}a_{2,1}...a_{1000,1}a_{1,2}...a_{1000,2}...a_{1000,1000}\) ?

Exercício 12 do Capítulo 5 do livro "The art of computer programming - Volume 3 - 2ª Edição" de Donald E. Knuth, na página 6.

Compartilhe

1 Resposta

0 votos
respondida Set 23 por Alan Antunes Rosendo (26 pontos)  
editado Set 24 por Alan Antunes Rosendo

O exercício pode ser resolvido fazendo uma matriz transposta.
No caso, defino uma nova matriz invertendo a quantidade de elementos na coluna e na linha, em relação a matriz original:

import numpy as np
tamanho=np.shape(a)
linhas=tamanho[1]
colunas=tamanho[0]
matriz=np.zeros((linhas,colunas))

Posteriormente eu coloco os elementos dessa nova matriz para corresponderem ao da antiga invertendo a linha e a coluna:

    for i in range(linhas):
      for j in range(colunas):
        matriz[i,j]=a[j,i]

O código completo, com a definição da função ficou:

def transpose(a):
  import numpy as np
  tamanho=np.shape(a)
  linhas=tamanho[1]
  colunas=tamanho[0]
  matriz=np.zeros((linhas,colunas))
  for i in range(linhas):
     for j in range(colunas):
          matriz[i,j]=a[j,i]
  return matriz

Implementando a matriz da questão e uma outra matriz não quadrada para testar a função criada, temos:

if __name__ == '__main__':
  import numpy as np
  #Testando uma matriz conforme a da questão
  mat1=np.random.random((1000,1000))
  print(f'a matriz original é:\n{mat1}')
  print(f'a matriz transposta é:\n{transpose(mat1)}')
  #Testando para matriz não quadradada:
  mat2=np.random.random((3,5))
  print(f'a matriz não quadrada original é:\n{mat2}')
  print(f'a matriz não quadrada transposta é:\n{transpose(mat2)}')

Havia interpretado a questão de forma errada, a questão fornece uma lista, daí é necessário converter a lista em matriz, posteriormente fazer a transposta e transformá-la novamente em lista.

Continuando a solução, criando a função para transformar a lista em uma matriz, temos:

def matriz(n):
  c=np.array([n]).reshape(int(len(n)**.5),int(len(n)**.5))
  return c

Finalmente faço uma função que chama as duas funções criadas anteriormente e transforma o resultado final em uma lista:

def convert(b):
  mat=matriz(b) #transforma a entrada em uma matriz
  mattrans=transpose(mat) #cria a matriz transposta
  lista=list(mattrans.flatten()) #transforma a matriz transposta em uma lista novamente
  print(lista)

Testando a função convert em dois casos (um caso mais simples que facilita a visualização e outro com um exemplo do tamanho da questão, temos:

if __name__ == '__main__':
  #Simulação com uma lista menor para facilitar a visualização
  n=[11,12,13,21,22,23,31,32,33]
  convert(n)
  #Simulação com uma lista aleatória do tamanho lista da questão
  tamanho=1000*1000
  valores=(range(0,10))
  lista2=choices(valores,k=tamanho)
  convert(lista2)
comentou Set 23 por danielcajueiro (5,486 pontos)  
Alan, de onde é essa questão? Vc precisa colocar a referência. Livro, capitulo, pagina.
comentou Set 23 por Alan Antunes Rosendo (26 pontos)  
Havia esquecido, inclui agora a referência.
comentou Set 23 por Fabio Fujita (36 pontos)  
Olá Alan.

A solução que você apresentou considera que foi apresentada uma matriz e deseja-se encontrar a matriz transposta. Partindo dessa premissa, você implementou a transposição de uma matriz usando dois loops.

A proposta do exercício me parece ser outra. Pelo que entendi, temos uma lista com um milhão de valores (1000 vezes 1000), em que os primeiros n elementos da lista representam os elementos da primeira linha de uma matriz, os elementos n+1 a 2n da lista representam os elementos da segunda linha da matriz, e assim sucessivamente. Ele pede para que seja obtida uma nova lista em que os primeiros n elementos sejam os elementos da primeira coluna da matriz, os elementos n+1 a 2n da lista representem os elementos da segunda coluna da matriz, e assim sucessivamente. A idéia é a mesma de uma transposição, mas a forma de representação é diferente.

Há várias formas que isso poderia ser feito. Algumas delas são:
 
1. Atribuir uma chave (j,i) para cada elemento aij e posteriormente reordenar a lista de acordo com essa chave (sorting), para obter a lista que representa a matriz transposta.

2. Outra forma (com custo maior) seria quebrar a lista em n listas de n elementos (a primeira lista com os elementos 1 a n, a segunda lista com os elementos n+1 a 2n, e assim sucessivamente). A lista que representa a matriz transposta poderia então ser obtida usando loops e o comando append, adicionando o primeiro elemento da primeira lista, o primeiro elemento da segunda lista e assim sucessivamente, até que todos os elementos tenham sido inseridos.

3. Caso queira insistir na sua solução, você pode fazer a leitura de uma lista convertendo-a em uma matriz, obtendo a transposta e posteriormente convertendo essa matriz novamente em uma lista. Isso é, de certa forma, equivalente à proposta 1, que atribui chaves a cada um dos elementos.

Espero ter ajudado.
comentou Set 24 por Alan Antunes Rosendo (26 pontos)  
Obrigado! Eu havia interpretado a questão de forma errada, inclui outras funções para complementar a resposta.
comentou Set 24 por Fabio Fujita (36 pontos)  
Olá Alan.

Vi que você alterou a solução para partir de uma lista que representa uma matriz e chegar a uma lista que representa a matriz transposta, conforme o exercício pedia.

A sua implementação resolverá o problema proposto no enunciado, mas acho que vale a ressalva de que a forma como está definida a função "matriz" funcionará apenas para matrizes quadradas. Caso queira deixar a solução mais geral, uma alternativa seria passar diretamente para a função o número de linhas e colunas da matriz que a lista de valores representa.

Um abraço.
...