Descripción del desafío

Comencemos con algunas definiciones:

• una relación es un conjunto de pares de elementos ordenados (en este desafío, usaremos enteros)

Por ejemplo, [(1, 2), (5, 1), (-9, 12), (0, 0), (3, 2)]es una relación.

• una relación se llama transitiva si para cualquiera de los dos pares de elementos (a, b)y (b, c)en esta relación, un par (a, c)también está presente,

• [(1, 2), (2, 4), (6, 5), (1, 4)]es transitivo, porque contiene (1, 2)y (2, 4), pero (1, 4)también,

• [(7, 8), (9, 10), (15, -5)]es transitivo, porque no hay dos pares (a, b), (c, d)presente tal que b= c.

• [(5, 9), (9, 54), (0, 0)]no es transitivo, porque contiene (5, 9)y (9, 54), pero no(5, 54)

Dada una lista de pares de enteros, determine si una relación es transitiva o no.

De entrada y salida

Se le dará una lista de pares de enteros en cualquier formato razonable. Considera una relación

[(1, 6), (9, 1), (6, 5), (0, 0)]

Los siguientes formatos son equivalentes:

[(1, 6), (9, 1), (6, 5), (0, 0)] # list of pairs (2-tuples)
[1, 9, 6, 0], [6, 1, 5, 0] # two lists [x1, x2, ..., xn] [y1, y2, ..., yn]
[[1, 6], [9, 1], [6, 5], [0, 0] # two-dimentional int array
[4, 1, 6, 9, 1, 6, 5, 0, 0] # (n, x1, y1, ..., xn, yn)
[1+6i, 9+i, 6+5i, 0+0i] # list of complex numbers

... many others, whatever best suits golfing purposes

Salida: un valor verdadero para una relación transitiva, falsa de lo contrario. Puede suponer que la entrada consistirá en al menos un par, y que los pares son únicos.

Haskell, 42 bytes

f x=and[elem(a,d)x|(a,b)<-x,(c,d)<-x,b==c]

Ejemplo de uso: f [(1,2), (2,4), (6,5), (1,4)]-> True.

Bucle (externo) sobre todos los pares (a,b)y bucle (interno) sobre los mismos pares, ahora llamados (c,d)y cada vez que se b==cverifica si (a,d)también existe un par existente. Combina los resultados con lógico and.

 Prólogo, 66 bytes

t(L):-not((member((A,B),L),member((B,C),L),not(member((A,C),L)))).

La relación no es transitiva si podemos encontrar (A, B) y (B, C) de modo que (A, C) no se mantenga.

MATL , 27 25 bytes

7#u2e!l6MX>thl4$XQttY*g<~

El formato de entrada es una matriz (que se usa ;como separador de filas) donde cada par de la relación es una columna. Por ejemplo, casos de prueba

[(1, 2), (2, 4), (6, 5), (1, 4)]
[(7, 8), (9, 10), (15, -5)]
[(5, 9), (9, 54), (0, 0)]

se introducen respectivamente como

[1 2 6 1; 2 4 5 4]
[7 9 15; 8 10 -5]
[5 9 0; 9 54 0]

La salida de verdad es una matriz formada por unos. Falsy es una matriz que contiene al menos un cero.

Pruébalo en línea!

Explicación

El código primero reduce los enteros de entrada a valores enteros únicos basados ​​en 1. A partir de esos valores, genera la matriz de adyacencia; la matriz lo multiplica por sí mismo; y convierte valores distintos de cero en la matriz de resultados a unos. Finalmente, verifica que ninguna entrada en la última matriz exceda la de la matriz de adyacencia.

JavaScript (ES6), 69 67 bytes

a=>(g=f=>a.every(f))(([b,c])=>g(([d,e])=>c-d|!g(([d,c])=>b-d|c-e)))

Ahorró 2 bytes gracias a una idea de @Cyoce. Había cuatro formulaciones anteriores de 69 bytes:

a=>a.every(([b,c])=>a.every(([d,e])=>c-d|a.some(([d,c])=>b==d&c==e)))
a=>!a.some(([b,c])=>!a.some(([d,e])=>c==d&a.every(([d,c])=>b-d|c-e)))
a=>a.every(([b,c])=>a.every(([d,e])=>c-d|!a.every(([d,c])=>b-d|c-e)))
(a,g=f=>a.every(f))=>g(([b,c])=>g(([d,e])=>c-d|!g(([d,c])=>b-d|c-e)))

Brachylog , 24 bytes

'{psc[A:B:B:C],?'e[A:C]}

Pruébalo en línea!

Explicación:

'{psc[A:B:B:C],?'e[A:C]}
'{                     } it is impossible to find
    c                    a flattened
   s                     subset of
  p                      a permutation of the input
     [A:B:B:C]           that has four elements, with the second and third equal
              ,?         and such that the input
                'e       does not contain
                  [A:C]  a list formed of the first and fourth element

En otras palabras, si la entrada contiene pares [A:B]y [B:C], podemos permutar la entrada para poner [A:B]y [B:C]al principio, eliminar todos los demás elementos y generar una lista [A:B:B:C]. Luego devolvemos la verdad del predicado interno (falsey de todo el programa) si [A:C]no está allí.

CJam (22 bytes)

{__Wf%m*{z~~=*}%\-e_!}

Conjunto de pruebas en línea . Este es un bloque anónimo (función) que toma los elementos como una matriz de dos niveles, pero el conjunto de pruebas realiza la manipulación de cadenas para poner primero la entrada en un formato adecuado.

Disección

{         e# Begin a block
  _       e#   Duplicate the argument
  _Wf%    e#   Duplicate again and reverse each pair in this copy
  m*      e#   Cartesian product
  {       e#   Map over arrays of the form [[a b][d c]] where [a b] and [c d]
          e#   are in the relation
    z~~=* e#     b==c ? [a d] : []
  }%
  \-      e#   Remove those transitive pairs which were in the original relation
  e_!     e#   Test that we're only left with empty arrays
}

Pyth, 14 bytes

!-eMfqFhTCM*_M

Banco de pruebas

Se espera que el formato de entrada sea [[0, 0], [0, 1], ... ]

!-eMfqFhTCM*_M
!-eMfqFhTCM*_MQQQ    Variable introduction
            _MQ      Reverse all of the pairs
           *   Q     Cartesian product with all of the pairs
         CM          Transpose. We now have [[A2, B1], [A1, B2]] for each pair
                     [A1, A2], [B1, B2] in the input.
    f                Filter on
       hT            The first element (the middle two values)
     qF              Being equal
  eM                 Take the end of all remaining elements (other two values)
 -              Q    Remove the pairs that are in the input
!                    Negate. True if no transitive pairs were not in the input

Mathematica, 49 bytes

#/.{x=___,{a_,b_},x,{b_,c_},x}/;#~FreeQ~{a,c}:>0&

Función pura que toma una lista de pares. Si la lista de entrada contiene {a,b}y {b,c}no es {a,c}para algunos a, b, c, la reemplaza por 0. La verdad es la lista de entrada, la falsedad es 0.

C ++ 14, 140 bytes

Como lambda sin nombre que regresa a través del parámetro de referencia. Requiere su entrada para ser un contenedor de pair<int,int>. Tomando el aburrido enfoque O (n ^ 3).

[](auto m,int&r){r=1;for(auto a:m)for(auto b:m)if (a.second==b.first){int i=0;for(auto c:m)i+=a.first==c.first&&b.second==c.second;r*=i>0;}}

Sin golf y uso:

#include<vector>
#include<iostream>

auto f=
[](auto m,int&r){
  r=1;                         //set return flag to true
  for(auto a:m)                //for each element
    for(auto b:m)              //check with second element
      if (a.second==b.first){  //do they chain?
        int i=0;               //flag for local transitivity
        for(auto c:m)          //search for a third element
          i+=a.first==c.first&&b.second==c.second;
        r*=i>0;                //multiply with flag>0, resulting in 0 forever if one was not found
      }
}
;

int main(){
 std::vector<std::pair<int,int>> m={
  {1, 2}, {2, 4}, {6, 5}, {1, 4}
 };

 int r;
 f(m,r);
 std::cout << r << std::endl;

 m.emplace_back(3,6);
 f(m,r);
 std::cout << r << std::endl;

 m.emplace_back(3,5);
 f(m,r);
 std::cout << r << std::endl;

}

Python 2 , 91 67 55 bytes

lambda s:all(b-c or(a,d)in s for a,b in s for c,d in s)

Pruébalo en línea!

-24 bytes gracias a Leaky Nun
-12 bytes gracias a Bubbler

Axioma 103 bytes

c(x)==(for i in x repeat for j in x repeat if i.2=j.1 and ~member?([i.1, j.2],x)then return false;true)

sin golf:

c(x)==
  for i in x repeat
    for j in x repeat
       if i.2=j.1 and ~member?([i.1, j.2],x) then return false
  true

                                                                   Type: Void

los ejercicios

(2) -> c([[1,2],[2,4],[6,5],[1,4]])
   Compiling function c with type List List PositiveInteger -> Boolean
   (2)  true
                                                                Type: Boolean
(3) -> c([[7,8],[9,10],[15,-5]])
   Compiling function c with type List List Integer -> Boolean
   (3)  true
                                                            Type: Boolean
(4) -> c([[5,9],[9,54],[0,0]])
   Compiling function c with type List List NonNegativeInteger ->
      Boolean
   (4)  false

Pyth - 22 21 bytes

.Am},hdedQfqFtPTsM^Q2

Test Suite .

Clojure, 56 53 bytes

Actualización: en lugar de usarlo :when, lo comprobaré para todos los pares de [a b] [c d]cualquiera b != co [a d]se encuentra en el conjunto de entrada.

#(every? not(for[[a b]%[c d]%](=[b nil][c(%[a d])])))

Original:

Wow, Clojure para los bucles son geniales: D Esto comprueba que el forbucle no genera un valor falso, lo que ocurre si [a d]no se encuentra en el conjunto de entrada.

#(not(some not(for[[a b]%[c d]% :when(= b c)](%[a d]))))

Esta entrada tiene que ser un conjunto de vectores de dos elementos:

(f (set [[1, 2], [2, 4], [6, 5], [1, 4]]))
(f (set [[7, 8], [9, 10], [15, -5]]))
(f (set [[5, 9], [9, 54], [0, 0]]))

Si la entrada debe ser similar a una lista, (%[a d])debe reemplazarse por ((set %)[a d])6 bytes adicionales.

Ambas soluciones son funciones sin nombre que toman una lista de pares ordenados como entrada y retorno Trueo False.

Mathematica, 65 bytes

SubsetQ[#,If[#2==#3,{#,#4},Nothing]&@@@Join@@@#~Permutations~{2}]&

#~Permutations~{2}]crea la lista de todos los pares ordenados de pares ordenados a partir de la entrada y los Join@@@convierte en cuádruples ordenados. Esos son operados por la función If[#2==#3,{#,#4},Nothing]&@@@, que tiene una propiedad genial: si los dos elementos del medio son iguales, devuelve el par ordenado que consiste en el primer y el último número; de lo contrario, regresa Nothing, un token especial de Mathematica que desaparece automáticamente de las listas. Entonces, el resultado es el conjunto de pares ordenados que necesita estar en la entrada para que sea transitivo; SubsetQ[#,...]detecta esa propiedad

Mathematica, 70 bytes

And@@And@@@Table[Last@i!=#&@@j||#~MemberQ~{#&@@i,Last@j},{i,#},{j,#}]&

Table[...,{i,#},{j,#}]crea una matriz 2D indexada por iy j, que se toman directamente de la entrada (por lo tanto, ambos son pares ordenados). La función de esos dos índices es Last@i!=#&@@j||#~MemberQ~{#&@@i,Last@j}, que se traduce como "el segundo elemento de iy el primer elemento de jno coinciden, o la entrada contiene el par ordenado que consiste en el primer elemento de iy el último elemento de j". Esto crea una matriz 2D de booleanos, que se And@@And@@@aplana en un solo booleano.

APL (NARS), 39 caracteres, 78 bytes

{∼∨/{(=/⍵[2 3])∧∼(⊂⍵[1 4])∊w}¨,⍵∘.,w←⍵}

prueba:

  f←{∼∨/{(=/⍵[2 3])∧∼(⊂⍵[1 4])∊w}¨,⍵∘.,w←⍵}
  f (1 2) (2 4) (6 5) (1 4)
1
  f (7 8) (9 10) (15 ¯5)
1
  f (5 9) (9 54) (0 0)
0

un segundo 'solución' sigue goto maneras:

r←q w;i;j;t;v
r←1⋄i←0⋄k←↑⍴w⋄→3
r←0⋄→0
→0×⍳k<i+←1⋄t←i⊃w⋄j←0
→3×⍳k<j+←1⋄v←j⊃w⋄→4×⍳t[2]≠v[1]⋄→2×⍳∼(⊂t[1]v[2])∊w

Lisp común, 121 bytes

(lambda(x)(not(loop for(a b)in x thereis(loop for(c d)in x do(if(= b c)(return(not(member`(,a ,d) x :test #'equal))))))))

Pruébalo en línea!