Herausforderungsbeschreibung

Beginnen wir mit einigen Definitionen:

• Eine Relation ist eine Menge geordneter Elementpaare (in dieser Herausforderung werden Ganzzahlen verwendet).

Zum Beispiel [(1, 2), (5, 1), (-9, 12), (0, 0), (3, 2)]ist eine Beziehung.

• eine Beziehung heißt transitive wenn für irgendwelche zwei Paare von Elementen (a, b)und (b, c)in dieser Beziehung ein Paar (a, c)ebenfalls vorhanden ist,

• [(1, 2), (2, 4), (6, 5), (1, 4)]ist transitiv, weil es enthält (1, 2)und (2, 4), aber (1, 4)auch,

• [(7, 8), (9, 10), (15, -5)]ist transitiv, weil es keine zwei Paare gibt (a, b), die so (c, d)vorhanden sind, dass b= c.

• [(5, 9), (9, 54), (0, 0)]ist nicht transitiv, weil es (5, 9)und enthält (9, 54), aber nicht(5, 54)

Bestimmen Sie anhand einer Liste von Ganzzahlpaaren, ob eine Beziehung transitiv ist oder nicht.

Input-Output

Sie erhalten eine Liste mit Paaren von ganzen Zahlen in einem angemessenen Format. Betrachten Sie eine Beziehung

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

Die folgenden Formate sind äquivalent:

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

Ausgabe: ein wahrer Wert für eine transitiven Beziehung, sonst falsch. Sie können davon ausgehen, dass die Eingabe aus mindestens einem Paar besteht und dass die Paare eindeutig sind.

Haskell, 42 Bytes

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

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

(Äußere) Schleife über alle Paare (a,b)und (innere) Schleife über dieselben Paare, die jetzt aufgerufen werden (c,d)und jedes Mal, wenn b==cüberprüft wird, ob (a,d)es sich auch um ein vorhandenes Paar handelt. Kombinieren Sie die Ergebnisse mit logisch and.

 Prolog, 66 Bytes

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

Die Beziehung ist nicht transitiv, wenn wir (A, B) und (B, C) so finden, dass (A, C) nicht gilt.

MATL , 27 25 Bytes

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

Das Eingabeformat ist eine Matrix (die ;als Zeilentrennzeichen verwendet wird), wobei jedes Beziehungspaar eine Spalte ist. Zum Beispiel Testfälle

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

werden jeweils eingegeben als

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

Die Wahrheitsausgabe ist eine aus Einsen gebildete Matrix. Falsy ist eine Matrix, die mindestens eine Null enthält.

Probieren Sie es online!

Erläuterung

Der Code reduziert zuerst die Eingabe-Ganzzahlen auf eindeutige, 1-basierte Ganzzahlwerte. Aus diesen Werten wird die Adjazenzmatrix generiert. Matrix multipliziert es mit sich selbst; und wandelt Werte ungleich Null in der Ergebnismatrix in Einsen um. Schließlich wird geprüft, ob kein Eintrag in der letzteren Matrix den in der Adjazenzmatrix überschreitet.

JavaScript (ES6), 69 bis 67 Byte

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

2 Bytes gespart dank einer Idee von @Cyoce. Es gab vier vorherige 69-Byte-Formulierungen:

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

Probieren Sie es online!

Erläuterung:

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

Mit anderen Worten, wenn die Eingabe Paare [A:B]und enthält [B:C], können wir zulassen, dass die Eingabe alle anderen Elemente setzt [A:B]und [B:C]am Anfang löscht und eine Liste erstellt [A:B:B:C]. Dann kehren wir wahrheitsgemäß vom inneren Prädikat (Falsch aus dem gesamten Programm) zurück, wenn [A:C]es nicht da ist.

CJam (22 Bytes)

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

Online-Testsuite . Dies ist ein anonymer Block (eine Funktion), der die Elemente als Array mit zwei Ebenen verwendet. Die Testsuite führt jedoch eine Zeichenfolgenmanipulation durch, um die Eingabe zuerst in ein geeignetes Format zu bringen.

Präparation

{         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

Testsuite

Das Eingabeformat wird erwartet [[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&

Reine Funktion, die eine Liste von Paaren benötigt. Wenn die Eingangsliste enthält {a,b}und , {b,c}aber nicht {a,c}für einige a, b, c, ersetzt sie durch 0. Wahrheit ist die Eingabeliste, falsch ist 0.

C ++ 14, 140 Bytes

Als unbenanntes Lambda, das über den Referenzparameter zurückkehrt. Erfordert, dass seine Eingabe ein Container von ist pair<int,int>. Den langweiligen O (n ^ 3) -Ansatz wählen.

[](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 und Nutzung:

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

Probieren Sie es online!

-24 Bytes dank Leaky Nun
-12 Bytes dank Bubbler

Axiom 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

die Übungen

(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

Update: Anstatt zu verwenden, :whenüberprüfe ich einfach, ob für alle Paare von [a b] [c d]entweder b != coder [a d]aus dem Eingabesatz gefunden wird.

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

Original:

Wow, Clojure für Schleifen ist cool: D Hiermit wird überprüft, ob die forSchleife keinen falschen Wert generiert, der auftritt, wenn er [a d]nicht aus der Eingabemenge gefunden wird.

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

Diese Eingabe muss aus zwei Elementen bestehen:

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

Wenn die Eingabe listenartig sein (%[a d])muss, muss sie durch ((set %)[a d])zusätzliche 6 Bytes ersetzt werden.

Beide Lösungen sind unbenannte Funktionen, die eine Liste geordneter Paare als Eingabe und Rückgabe von Trueoder verwenden False.

Mathematica, 65 Bytes

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

#~Permutations~{2}]Erstellt die Liste aller geordneten Paare von geordneten Paaren aus der Eingabe und Join@@@konvertiert diese in geordnete Vierfache. Diese werden dann von der Funktion bearbeitet If[#2==#3,{#,#4},Nothing]&@@@, die eine coole Eigenschaft hat: Wenn die beiden mittleren Elemente gleich sind, gibt sie das geordnete Paar zurück, das aus der ersten und der letzten Zahl besteht. Andernfalls Nothingwird ein spezielles Mathematica-Token zurückgegeben, das automatisch aus Listen verschwindet. Das Ergebnis ist also die Menge der geordneten Paare, die in der Eingabe enthalten sein müssen, damit sie transitiv sind. SubsetQ[#,...]erkennt diese Eigenschaft.

Mathematica, 70 Bytes

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

Table[...,{i,#},{j,#}]Erstellt ein mit iund indiziertes 2D-Array j, das direkt aus der Eingabe entnommen wird (daher sind beide geordnete Paare). Die Funktion dieser beiden Indizes lautet Last@i!=#&@@j||#~MemberQ~{#&@@i,Last@j}: "Entweder stimmen das zweite Element von iund das erste Element von jnicht überein, oder die Eingabe enthält das geordnete Paar, das aus dem ersten Element von iund dem letzten Element von besteht. j" Dadurch wird ein 2D-Array von Booleschen Werten erstellt, das And@@And@@@zu einem einzigen Booleschen Wert zusammengefasst wird .

APL (NARS), 39 Zeichen, 78 Byte

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

Prüfung:

  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

eine Sekunde 'Lösung' folgen Sie goto Möglichkeiten:

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

Common Lisp, 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))))))))

Probieren Sie es online!