Reconocimiento de relaciones funcionales entre dos conjuntos

Una relación binaria entre dos conjuntos A y B se puede representar mediante un conjunto de pares (a,b) tales que a ∈ A y b ∈ B. Por ejemplo, la relación < entre A = {1,5,3} y B = {0,2,4} se representa por {(1,2),(1,4),(3,4)}.

Una relación R entre A y B es funcional si cada elemento de A está relacionado mediante R como máximo con un elemento de B. Por ejemplo, [(2,4),(1,5),(3,4)] es funcional, pero [(3,4),(1,4),(1,2),(3,4)] no lo es.

Definir la función

tal que (esFuncional r) se verifica si la relación r es funcional. Por ejemplo,

Soluciones

8 Comentarios

    1. Tu función es O(n^2), ya que nub es O(n^2), y la mía usa sort que es O(n (log n)).

      La función mas eficiente creo que sería ir elemento a elemento sacándolo de la lista y metiéndolo en una caja correspondiente, inicialmente vacía, y comparando si es diferente al elemento que hay en la caja, en ese caso la respuesta es False y en caso contrario desechamos el elemento y seguimos sacando elementos de la lista y metiéndolos en sus cajas. Esta función es lineal pero quizá abusa demasiado de memoria. Aunque realmente mi problema es que no sabría implementarla en Haskell. :/

Leave a Reply to alvblamolCancel reply