Dependencias Funcionales W37218

Sea una matriz $n \times m$ de enteros. Esta matriz representa una tabla de datos de $n$ filas y $m$ columnas ($n \geq 2$ y $m \geq 2$).

Decimos que la dependencia funcional x -> y entre dos columnas x y y, es válida en la matriz M si y solo si para todo par de filas i y j (donde $i < j$) ocurre lo siguiente:

Por ejemplo, sea la tabla (matriz) M de 5 filas y 4 columnas:

Consideremos la dependencia funcional 0 -> 1. Vemos que los valores de la columna 0 coinciden en las filas 0 y 2:

y también en las filas 3 y 4:

Y vemos que en ambos casos los valores de la columna 1 también son iguales. Y esto ocurre para todo par de filas. Por tanto, la dependencia funcional 0 -> 1 es válida.

En cambio, la dependencia funcional 0 -> 3 no es válida porque aunque, por ejemplo, los valores de las columnas 0 y 3 coinciden en las filas 0 y 2:

no ocurre lo mismo en las filas 3 y 4, en las que coinciden los valores de la columna 0, pero no los valores de la columna 3:

En este caso, podemos decir que las filas 3 y 4 invalidan 0 -> 3.

Tened en cuenta que, dada una dependencia funcional x -> y (donde x y y son identificadores de columnas), si los valores de x no coinciden en dos filas, entonces estas dos filas no pueden invalidar la dependencia funcional, independientemente de si los valores de la columna y son o no iguales. Por ejemplo, las filas 0 y 1 no tienen el mismo valor en la columna 0:

Por tanto, no pueden invalidar la dependencia 0 -> 1 aunque el valor de la columna 1 tampoco coincida.

Haz una función dependencia_funcional con la siguiente declaración y especificación:

/*
 * PRE:  M.size() > 0 and M[0].size() > 0 and 0 <= x,y < M[0].size().
 *
 * POST: Devuelve true si y solo si la dependencia funcional x -> y
 *       es válida en la matriz M.
 */
bool dependencia_funcional(const Matriu& M, int x, int y);

Observación

Solo hay que enviar la función que se pide (y las funciones que hayáis podido declarar vosotros).

Además, en el fichero que enviéis debe aparecer también esto:

#include <iostream>
#include <vector>
using namespace std;

typedef vector <int>   Vector;
typedef vector<Vector> Matriu;

No se puede usar la ordenación de C++: std::sort. Tampoco se puede usar el método push_back() de la clase vector.

Si queréis, podéis usar las funciones min, max o swap.

Hay que tener en cuenta que la relación entre dos filas i y j respecto a la dependencia x -> y es simétrica. Es decir, si el par de filas i y j no invalidan la dependencia x -> y, el par j y i tampoco. Por eso en la definición de la dependencia especificamos $i < j$.

Entrada

La entrada es una matriz y una secuencia de dependencias funcionales. De la lectura ya se encarga el programa principal.

Salida

La salida son los resultados para cada dependencia funcional. De la escritura también se encarga el programa principal.