Matriz dodecafónica

Como se explica en Create a Twelve-Tone Melody With a Twelve-Tone Matrix una matriz dodecafónica es una matriz de 12 filas y 12 columnas construidas siguiendo los siguientes pasos:

  • Se escribe en la primera fila una permutación de los números del 1 al 12. Por ejemplo,

  • Escribir la primera columna de forma que, para todo i (entre 2 y 12), a(i,1) es el número entre 1 y 12 que verifica la siguiente condición

Siguiendo con el ejemplo anterior, la matriz con la 1ª fila y la 1ª columna es

  • Escribir la segunda fila de forma que, para todo j (entre 2 y 12), a(j,2) es el número entre 1 y 12 que verifica la siguiente condición

Siguiendo con el ejemplo anterior, la matriz con la 1ª fila, 1ª columna y 2ª fila es

  • Las restantes filas se completan como la 2ª; es decir, para todo i (entre 3 y 12) y todo j (entre 2 y 12), a(i,j) es el número entre 1 y 12 que verifica la siguiente relación.

Siguiendo con el ejemplo anterior, la matriz dodecafónica es

Definir la función

tal que (matrizDodecafonica xs) es la matriz dodecafónica cuya primera fila es xs (que se supone que es una permutación de los números del 1 al 12). Por ejemplo,

Comprobar con QuickCheck para toda matriz dodecafónica D se verifican las siguientes propiedades:

  • todas las filas de D son permutaciones de los números 1 a 12,
  • todos los elementos de la diagonal de D son iguales y
  • la suma de todos los elementos de D es 936.

Nota: Este ejercicio ha sido propuesto por Francisco J. Hidalgo.

Soluciones

Pensamiento

Como el olivar,
mucho fruto lleva,
poca sombra da.

Antonio Machado

Matriz girada 180 grados

Definir la función

tal que (matrizGirada180 p) es la matriz obtenida girando 180 grados la matriz p. Por ejemplo,

Soluciones

Pensamiento

Bueno es recordar
las palabras viejas
que han de volver a sonar.

Antonio Machado

Representaciones de grafos

Los grafos no dirigidos puede representarse mediante matrices de adyacencia y también mediante listas de adyacencia. Por ejemplo, el grafo

se puede representar por la matriz de adyacencia

donde el elemento (i,j) es 1 si hay una arista entre los vértices i y j y es 0 si no la hay. También se puede representar por la lista de adyacencia

donde las primeras componentes son los vértices y las segundas la lista de los vértices conectados.

Definir las funciones

tales que

  • (matrizAlista a) es la lista de adyacencia correspondiente a la matriz de adyacencia a. Por ejemplo, definiendo la matriz anterior por

se tiene que

  • (listaAmatriz ps) es la matriz de adyacencia correspondiente a la lista de adyacencia ps. Por ejemplo,

Soluciones

Representación ampliada de matrices dispersas

En el ejercicio anterior se explicó una representación reducida de las matrices dispersas. A partir del número de columnas y la representación reducida se puede construir la matriz.

Definir la función

tal que (ampliada n xss) es la matriz con n columnas cuya representación reducida es xss. Por ejemplo,

Soluciones

Ampliación de una matriz

Definir, usando Data.Matrix, la función

tal que (ampliaMatriz p f c) es la matriz obtenida a partir de p repitiendo cada fila f veces y cada columna c veces. Por ejemplo, si ej1 es la matriz definida por

entonces

Nota: Este ejercicio está basado en el problema Skener de Kattis.

Soluciones

Conflictos de horarios

Los horarios de los cursos se pueden representar mediante matrices donde las filas indican los curso, las columnas las horas de clase y el valor correspondiente al curso i y la hora j es verdadero indica que i tiene clase a la hora j.

En Haskell, podemos usar la matrices de la librería Data.Matrix y definir el tipo de los horarios por

Un ejemplo de horario es

en el que el 1º curso tiene clase a la 1ª y 2ª hora, el 2º a la 2ª y a la 3ª y el 3º a la 3ª y a la 4ª.

Definir la función

tal que (cursosConflictivos h is) se verifica para si los cursos de la lista is hay alguna hora en la que más de uno tiene clase a dicha hora. Por ejemplo,

Soluciones

Diagonales de matrices como listas

Las matrices se pueden representar como listas de listas de la misma longitud, donde cada uno de sus elementos representa una fila de la matriz.

Definir la función

tal que (diagonal xss) es la diagonal de la matriz xss. Por ejemplo,

Soluciones

Solución con Maxima

Buscaminas

Enunciado

Soluciones

Referencia

El ejercicio está basado en Minesweeper de UVa Online Judge.