Descrição do Desafio

Vamos começar com algumas definições:

• uma relação é um conjunto de pares de elementos ordenados (neste desafio, usaremos números inteiros)

Por exemplo, [(1, 2), (5, 1), (-9, 12), (0, 0), (3, 2)]é uma relação.

• uma relação é chamada transitiva se, para quaisquer dois pares de elementos, (a, b)e (b, c)nessa relação, um par (a, c)também estiver presente,

• [(1, 2), (2, 4), (6, 5), (1, 4)]é transitivo, porque contém (1, 2)e (2, 4), mas (1, 4)também,

• [(7, 8), (9, 10), (15, -5)]é transitivo, porque não existem dois pares (a, b), (c, d)presentes de modo que b= c.

• [(5, 9), (9, 54), (0, 0)]não é transitivo, porque contém (5, 9)e (9, 54), mas não(5, 54)

Dada uma lista de pares de números inteiros, determine se uma relação é transitiva ou não.

Entrada / saída

Você receberá uma lista de pares de números inteiros em qualquer formato razoável. Considere uma relação

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

Os seguintes formatos são 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

Saída: um valor verdadeiro para uma relação transitiva, caso contrário, falsamente. Você pode assumir que a entrada consistirá em pelo menos um par e que os pares são únicos.

Haskell, 42 bytes

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

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

Loop (externo) sobre todos os pares (a,b)e loop (interno) sobre os mesmos pares, agora chamados (c,d)e sempre que b==cverificar se (a,d)também existe um par. Combine os resultados com lógico and.

 Prolog, 66 bytes

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

A relação não é transitiva se pudermos encontrar (A, B) e (B, C) de modo que (A, C) não seja válido.

MATL , 27 25 bytes

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

O formato de entrada é uma matriz (usando ;como separador de linhas) em que cada par da relação é uma coluna. Por exemplo, casos de teste

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

são respectivamente inseridos como

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

A saída de verdade é uma matriz formada por uns. Falsy é uma matriz que contém pelo menos um zero.

Experimente online!

Explicação

O código primeiro reduz os números inteiros de entrada para valores inteiros únicos baseados em 1. A partir desses valores, gera a matriz de adjacência; a matriz multiplica por si mesma; e converte valores diferentes de zero na matriz de resultados em unidades. Por fim, verifica se nenhuma entrada na última matriz excede a entrada na matriz de adjacência.

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)))

Economizou 2 bytes graças a uma idéia de @Cyoce. Havia quatro formulações 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)))

Braquilog , 24 bytes

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

Experimente online!

Explicação:

'{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

Em outras palavras, se a entrada contiver pares [A:B]e [B:C], podemos permitir que a entrada coloque [A:B]e [B:C]no início, exclua todos os outros elementos e produza uma lista [A:B:B:C]. Em seguida, retornamos a verdade do predicado interno (falsey de todo o programa), se [A:C]não estiver lá.

CJam (22 bytes)

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

Conjunto de testes online . Este é um bloco anônimo (função) que leva os elementos como uma matriz de dois níveis, mas o conjunto de testes faz manipulação de cadeias para colocar a entrada em um formato adequado primeiro.

Dissecação

{         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
}

Pitão, 14 bytes

!-eMfqFhTCM*_M

Suíte de teste

É esperado que o formato de entrada seja [[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&

Função pura que leva uma lista de pares. Se a lista de entrada contiver {a,b}e {b,c}não {a,c}for para alguns a, b, c, substitua-a por 0. Verdade é a lista de entrada, é falso 0.

C ++ 14, 140 bytes

Como lambda sem nome, retornando via parâmetro de referência. Requer que sua entrada seja um contêiner de pair<int,int>. Adotando a abordagem O (n ^ 3) chata.

[](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;}}

Ungolfed e 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)

Experimente online!

-24 bytes graças a Leaky Nun
-12 bytes graças 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)

ungolfed:

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

Os exercícios

(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

Pitão - 22 21 bytes

.Am},hdedQfqFtPTsM^Q2

Conjunto de Teste .

Clojure, 56 53 bytes

Atualização: em vez de usar :when, apenas verificarei se todos os pares de [a b] [c d]um b != cou [a d]é encontrado no conjunto de entrada.

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

Original:

Uau, Clojure para loops é legal: D Isso verifica se o forloop não gera um valor falso, o que ocorre se [a d]não for encontrado no conjunto de entrada.

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

Essa entrada deve ser um conjunto de vetores de dois 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]]))

Se a entrada precisar ser do tipo lista, (%[a d])ela deverá ser substituída por ((set %)[a d])6 bytes adicionais.

Ambas as soluções são funções sem nome, recebendo uma lista de pares ordenados como entrada e retorno Trueou False.

Mathematica, 65 bytes

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

#~Permutations~{2}]cria a lista de todos os pares ordenados de pares ordenados a partir da entrada e os Join@@@converte em quádruplos ordenados. Esses são então operados pela função If[#2==#3,{#,#4},Nothing]&@@@, que possui uma propriedade interessante: se os dois elementos do meio forem iguais, ele retornará o par ordenado que consiste no primeiro e no último número; caso contrário, ele retornará Nothing, um token especial do Mathematica que desaparecerá automaticamente das listas. Portanto, o resultado é o conjunto de pares ordenados que precisam estar na entrada para serem transitivos;SubsetQ[#,...]detecta essa propriedade.

Mathematica, 70 bytes

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

Table[...,{i,#},{j,#}]cria uma matriz 2D indexada por ie j, que são obtidas diretamente da entrada (portanto, são ambos pares ordenados). A função desses dois índices é Last@i!=#&@@j||#~MemberQ~{#&@@i,Last@j}, que se traduz em "o segundo elemento ie o primeiro elemento de jnão coincidem, ou a entrada contém o par ordenado que consiste no primeiro elemento de ie no último elemento de j". Isso cria uma matriz 2D de booleanos, que And@@And@@@se transforma em um único booleano.

APL (NARS), 39 caracteres, 78 bytes

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

teste:

  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

um segundo 'solução' segue os seguintes caminhos:

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 comum, 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))))))))

Experimente online!