Tentukan apakah suatu relasi transitif

15

Deskripsi tantangan

Mari kita mulai dengan beberapa definisi:

  • sebuah relasi adalah satu set pasang memerintahkan elemen (dalam tantangan ini, kita akan menggunakan bilangan bulat)

Misalnya, [(1, 2), (5, 1), (-9, 12), (0, 0), (3, 2)]adalah suatu relasi.

  • suatu relasi disebut transitif jika untuk setiap dua pasang elemen (a, b)dan (b, c)dalam relasi ini, suatu pasangan (a, c)juga hadir,

  • [(1, 2), (2, 4), (6, 5), (1, 4)]transitif, karena mengandung (1, 2)dan (2, 4), tetapi (1, 4)juga,

  • [(7, 8), (9, 10), (15, -5)]bersifat transitif, karena tidak ada dua pasangan (a, b), (c, d)sajikan sedemikian sehingga b= c.

  • [(5, 9), (9, 54), (0, 0)]tidak transitif, karena mengandung (5, 9)dan (9, 54), tetapi tidak(5, 54)

Diberikan daftar pasangan bilangan bulat, tentukan apakah suatu relasi transitif atau tidak.

Input output

Anda akan diberi daftar pasangan bilangan bulat dalam format apa pun yang masuk akal. Pertimbangkan suatu hubungan

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

Format berikut ini setara:

[(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

Output: nilai kebenaran untuk hubungan transitif, jika tidak palsu. Anda dapat mengasumsikan bahwa input akan terdiri dari setidaknya satu pasangan, dan pasangan tersebut unik.

shooqie
sumber
Apakah input harus berupa format seperti daftar, atau bisakah itu merupakan adjacency - format seperti matriks?
xnor
Anda harus memiliki test case yang hanya transitif karena pasangan dipesan. Misalnya (1,3) (2,1) (3,4) (1,4) (2,4). Jika pasangan tidak dipesan, ini tidak akan transitif karena (2,3)tidak ada.
Martin Ender
1
@ MartinEnder Saya pikir Anda salah menafsirkan "pasangan yang dipesan". Saya tidak berpikir itu berarti pasangan dalam urutan - Saya pikir itu berarti setiap pasangan memiliki pesanan, pertama kemudian kedua.
isaacg
@isaacg itulah yang saya maksud. Dengan kata lain, test case saya hanya benar karena hubungannya secara implisit tidak simetris.
Martin Ender
Haruskah test case ketiga ( [(7, 8), (9, 10), (15, -5)]) tidak transitif?
wnnmaw

Jawaban:

8

Haskell, 42 byte

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

Contoh penggunaan: f [(1,2), (2,4), (6,5), (1,4)]-> True.

(Luar) loop atas semua pasangan (a,b)dan (dalam) loop atas pasangan yang sama, sekarang dipanggil (c,d)dan setiap kali b==cmemeriksa apakah (a,d)juga ada pasangan. Gabungkan hasilnya dengan logis and.

nimi
sumber
Jawaban yang paling mudah dibaca sejauh ini!
Lynn
@ Lynn Periksa jawaban Prolog, lalu ;-)
coredump
4

 Prolog, 66 byte

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

Relasi tidak transitif jika kita dapat menemukan (A, B) dan (B, C) sehingga (A, C) tidak berlaku.

coredump
sumber
4

MATL , 27 25 byte

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

Format input adalah matriks (menggunakan ;sebagai pemisah baris) di mana setiap pasangan relasi adalah sebuah kolom. Misalnya, uji kasus

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

masing-masing dimasukkan sebagai

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

Truthy output matriks yang dibentuk oleh orang-orang. Falsy adalah matriks yang mengandung setidaknya satu nol.

Cobalah online!

Penjelasan

Kode pertama mengurangi integer input ke nilai integer berbasis 1 yang unik. Dari nilai-nilai itu menghasilkan matriks adjacency; matrix-mengalikannya dengan sendirinya; dan mengonversi nilai-nilai bukan nol dalam matriks hasil menjadi matriks. Akhirnya, ia memeriksa bahwa tidak ada entri dalam matriks yang terakhir melebihi yang ada di matriks adjacency.

Luis Mendo
sumber
3

JavaScript (ES6), 69 67 byte

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

Disimpan 2 byte berkat sebuah ide oleh @Cyoce. Ada empat formulasi 69 byte sebelumnya:

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)))
Neil
sumber
1
Anda mungkin dapat mempersingkat solusi kedua dengan membuat singkatan untuk.every
Cyoce
@Cyoce Memang, Anda menghemat 3 byte setiap kali dengan menulis [e], jadi meskipun biayanya 8 byte untuk menetapkan eAnda masih menyimpan byte. Namun, saya melangkah lebih jauh dengan membuat singkatan a.every, yang menghemat byte kedua.
Neil
3

Brachylog , 24 byte

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

Cobalah online!

Penjelasan:

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

Dengan kata lain, jika input berisi pasangan [A:B]dan [B:C], kita dapat mengubah input untuk menempatkan [A:B]dan [B:C]pada awalnya, menghapus semua elemen lainnya, dan menghasilkan daftar [A:B:B:C]. Kemudian kita mengembalikan kebenaran dari predikat batin (falsey dari seluruh program) jika [A:C]tidak ada.


sumber
2

CJam (22 byte)

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

Test suite online . Ini adalah blok anonim (fungsi) yang mengambil elemen sebagai array dua tingkat, tetapi test suite melakukan manipulasi string untuk memasukkan input ke dalam format yang sesuai terlebih dahulu.

Pembedahan

{         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
}
Peter Taylor
sumber
2

Pyth, 14 byte

!-eMfqFhTCM*_M

Suite uji

Format input diharapkan [[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
isaacg
sumber
2

Mathematica, 49 byte

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

Fungsi murni yang mengambil daftar pasangan. Jika daftar input berisi {a,b}dan {b,c}tetapi tidak {a,c}untuk sebagian orang a, b, c, gantikan dengan 0. Kebenaran adalah daftar input, falsy adalah 0.

ngenisis
sumber
1

C ++ 14, 140 byte

Sebagai lambda tanpa nama kembali melalui parameter referensi. Membutuhkan inputnya untuk menjadi wadah pair<int,int>. Mengambil pendekatan O (n ^ 3) yang membosankan.

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

Tidak digabungkan dan digunakan:

#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;

}
Karl Napf
sumber
1

Python 2 , 91 67 55 byte

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

Cobalah online!

-24 bytes berkat Leaky Nun
-12 bytes berkat Bubbler

HyperNeutrino
sumber
67 byte (dan memperbaiki kode Anda dengan mengubah lambda xke lambda s.
Leaky Nun
@ LeakyNun Oh whoops, itu agak bodoh dari saya. Terima kasih!
HyperNeutrino
55 byte dengan membongkar pada fors.
Bubbler
@Ubbler oh keren terima kasih
HyperNeutrino
0

Aksioma 103 byte

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

Latihan

(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
RosLuP
sumber
0

Pyth - 22 21 byte

.Am},hdedQfqFtPTsM^Q2

Test Suite .

Maltysen
sumber
0

Clojure, 56 53 byte

Pembaruan: Alih-alih menggunakan :whensaya hanya akan memeriksa semua pasangan dari [a b] [c d]salah satu b != catau[a d] ditemukan dari set input.

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

Asli:

Wow, Clojure untuk loop keren: D Ini memeriksa bahwa forloop tidak menghasilkan nilai falsy, yang terjadi jika [a d]tidak ditemukan dari set input.

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

Input ini harus berupa kumpulan vektor dua elemen:

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

Jika input harus seperti daftar maka (%[a d])harus diganti dengan ((set %)[a d])tambahan 6 byte.

NikoNyrh
sumber
0

Kedua solusi ini adalah fungsi yang tidak disebutkan namanya dengan mengambil daftar pasangan yang dipesan sebagai masukan dan pengembalian Trueatau False.

Mathematica, 65 byte

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

#~Permutations~{2}]membuat daftar semua pasangan yang dipesan dari pasangan yang dipesan dari input, dan Join@@@mengonversinya menjadi empat kali lipat yang dipesan. Mereka kemudian dioperasikan oleh fungsi If[#2==#3,{#,#4},Nothing]&@@@, yang memiliki properti dingin: jika dua elemen tengah sama, itu mengembalikan pasangan yang diurutkan yang terdiri dari angka pertama dan terakhir; jika tidak kembaliNothing , token Mathematica khusus yang secara otomatis menghilang dari daftar. Jadi hasilnya adalah himpunan pasangan berurutan yang perlu di input agar transitif; SubsetQ[#,...]mendeteksi properti itu.

Mathematica, 70 byte

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

Table[...,{i,#},{j,#}]menciptakan array 2D yang diindeks oleh idan j, yang diambil langsung dari input (karenanya keduanya pasangan yang dipesan). Fungsi dari kedua indeks tersebut adalah Last@i!=#&@@j||#~MemberQ~{#&@@i,Last@j}, yang diterjemahkan menjadi "elemen kedua idan elemen pertama jtidak cocok, atau inputnya berisi pasangan berurutan yang terdiri dari elemen pertama idan elemen terakhir j". Ini menciptakan array 2D boolean, yang And@@And@@@rata menjadi boolean tunggal.

Greg Martin
sumber
0

APL (NARS), 39 karakter, 78 byte

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

uji:

  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

'solusi' satu detik ikuti cara goto:

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
RosLuP
sumber
0

Common Lisp, 121 byte

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

Cobalah online!

Renzo
sumber