Herausforderung

Bestimmen Sie anhand einer Menge Tvon Teilmengen einer endlichen Menge S={1,2,3,...,n}, ob Tes sich um eine Topologie handelt oder nicht.

Erläuterung

Die Potenzmenge P(S) einer Menge Sist die Menge aller Teilmengen von S. Einige Beispiele:

S = {}, P(S) = {{}}
S = {1}, P(S) = {{}, {1}}
S = {1,2}, P(S) = {{}, {1}, {2}, {1,2}}
S = {1,2,3}, P(S) = {{}, {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3}}

Eine Topologie T in der Gruppe Sist eine Teilmenge P(S)mit folgenden Eigenschaften:

• {}ist in Tund Sist inT
• Wenn Aund Bsind Tdann so ist ihre KreuzungA ∩ B
• Wenn Aund Bsind in Tdann so ist ihre Vereinigung A ∪ B*

_{^{* Diese Definition ist nicht ganz korrekt, aber sie gilt für endliche Mengen, was für die Zwecke dieser Herausforderung ausreicht. Das eigentliche Axiom würde auch unendliche Vereinigungen zulassen, aber das ist im endlichen Fall irrelevant.}}

Einzelheiten

• Sie können davon ausgehen, dass S = {1,2,...,n}(oder alternativ S = {0,1,...,n}) wo ndie größte Ganzzahl ist, die in den Mengen von erscheint T.
• Das Eingabeformat ist flexibel: Sie können eine Zeichenfolge, eine Liste von Listen oder einen Satz von Listen oder ein ähnliches Format verwenden, das Ihre Sprache verarbeiten kann. Sie können auch Sätze wie verwenden, S = {0,1,...,n}wenn es bequemer ist.
• Die Ausgabe muss wahr oder falsch sein.
• Sie dürfen n(oder alternativ n+1oder n-1) als zusätzliche Eingabe nehmen.
• Wenn Sie mit geordneten Listen arbeiten, können Sie davon ausgehen, dass die Nummern innerhalb eines Sets sortiert sind. Sie können auch davon ausgehen, dass die Liste eine bestimmte Reihenfolge hat (z. B. lexikografisch).
• Da wir Mengen darstellen, können Sie davon ausgehen, dass keine zwei Einträge ihrer Listendarstellung gleich sind.

Beispiele

Topologien

{{}}  over {}
{{},{1}} over {1}
P(S) over S (see in the explanation)
{{},{1},{1,2}} over {1,2}
{{},{1},{2,3},{1,2,3}} over {1,2,3}
{{1}, {1,2,3}, {1,4,5,6}, {1,2,3,4,5,6}, {}, {2,3}, {4,5,6}, {2,3,4,5,6}}
{{}, {1}, {2,3}, {2}, {4,5,6}, {5,6}, {5}, {2,5,6}, {2,5}, {1,5}, {1,2,3,4,5,6}, {1,2,3}, {1,2}, {1,4,5,6}, {1,5,6}, {1,2,5,6}, {2,3,4,5,6}, {2,3,5,6}, {2,3,5}, {1,2,3,5}, {2,4,5,6}, {1,2,5}, {1,2,3,5,6}, {1,2,4,5,6}}
{{}, {1}, {1,2}, {1,2,3}, {1,2,3,4}, {1,2,3,4,5}, {1,2,3,4,5,6}, {1,2,3,4,5,6,7}, {1,2,3,4,5,6,7,8}, {1,2,3,4,5,6,7,8,9}}
{{}, {1}, {1,2,3}, {1,2,3,4,5}, {1,2,3,4,5,6,7}, {1,2,3,4,5,6,7,8,9}}

Nicht-Topologien

{{1}} because {} is not contained
{{},{2}} because {1,2} is not contained
{{},{1,2},{2,3}} because the union {1,2,3} is not contained
{{},{1},{1,2},{2,3},{1,2,3}} because the intersection of {1,2} and {2,3} is not contained
{{},{1},{2},{3},{1,2},{2,3},{1,2,3}} because the union of {1} and {3} is not contained
{{}, {1}, {2,3}, {2}, {4,5,6}, {5,6}, {5}, {2,5,6}, {2,5}, {1,5}, {1,2,3,4,5,6}, {1,2,3}, {1,2}, {1,4,5,6}, {1,5,6}, {1,2,5,6}, {2,3,4,5,6}, {2,3,5,6}, {2,3,5}, {2,4,5,6}, {1,2,5}, {1,2,3,5,6}, {1,2,4,5,6}} because {1,2,3,5} is missing
{{}, {1}, {2}, {1,2,3}, {1,2,3,4,5}, {1,2,3,4,5,6,7}, {1,2,3,4,5,6,7,8,9}} because {1,2} is missing 

Python 2 , 117 99 97 91 Bytes

n,x=input();sum(set.union(*x))!=n*-~n/2>q
[map(x.index,(i-i,i|j,i&j))for i in x for j in x]

Probieren Sie es online!

Die Ausgabe erfolgt über den Exit-Code

Haskell , 95 89 74 78 Bytes

import Data.List
t#n=all(`elem`t)$sort<$>[1..n]:[]:([union,intersect]<*>t<*>t)

Probieren Sie es online!

Erläuterung:

                              ([union,intersect]<*>t<*>t) -- create all unions & intersections 
                    [1..n]:[]:                            -- add the empty list and the full list
             sort<$>                                --sort them all
                                -- (as 'union' does not necessarily produce sorted outputs)
all(`elem`t)$                   -- check whether they are all already contained

Mathematica, 87 73 66 63 Bytes

Outer[{#⋂#2,#⋃#2}&,#,#,1]~Flatten~2⋃{{},Range@#2}==#⋃#&

Nimmt [T, n]als Eingabe.

Erläuterung

{#⋂#2,#⋃#2}&

Funktion, die den Schnittpunkt und die Vereinigung der Eingaben zurückgibt

Outer[ ... ,#,#,1]

Ordnen Sie diese Funktion der Eingabeliste auf Ebene 1 zu.

... ~Flatten~2

Reduzieren Sie das Ergebnis (der OuterTeil gibt eine Reihe verschachtelter Lists zurück).

... ⋃{{},Range@#2}

Nehmen Sie die Vereinigung zwischen der abgeflachten Liste und {{}, S}. Dadurch werden Duplikate entfernt {}und Sder resultierenden Liste hinzugefügt.

... ==#⋃#

Überprüfen Sie, ob die Liste von oben mit der sortierten Version der Eingabe übereinstimmt.

MATL , 38 Bytes

!t~hXAs1>GXBXH2Z^!"@Z}Z|1MZ&hHm]vAGn~+

Die Eingabe ist eine binäre Matrix, in der jede Zeile eine Menge ist, jede Spalte ein Element ist und jeder Eintrag die Zugehörigkeit angibt. Zum Beispiel {{},{1},{1,2}}wird ausgedrückt als [0 0;1 0;1 1]. Verwenden Sie das verknüpfte Octave-Programm , um in dieses Format zu konvertieren.

Probieren Sie es online! Oder überprüfen Sie alle Testfälle .

Erläuterung

!        % Implicit input. Transpose
t~       % Push a negated copy
h        % Horizontally concatenate both matrices
XA       % All: true for columns containing only 1
s        % Sum
1>       % Does it exceed 1? If so, both the empty set and the total
         % set are in the input
G        % Push input again
XB       % Convert each row from binary to decimal. This gives a column
         % vector of numbers that encode each set's contents. Union and
         % intersection will be done as bitwise XOR and AND
XH       % Copy to clipboard H
2Z^!     % Cartesian square transposed: gives all pairs of numbers as
         % columns of a matrix
"        % For each column
  @      %   Push current column
  Z}     %   Split into the two numbers
  Z|     %   Bitwise XOR
  1M     %   Push the two numbers again
  Z&     %   Bitwise AND
  h      %   Concatenate the two results horizontally
  Hm     %   Are they members of the vector of encoded sets? This gives
         %   a row vector with the two results
]        % End
v        % Concatenate all stack contents into a vertical vector
A        % Does it only contain ones? This is the main result: true iff
         % input is a non-empty topology. The empty input gives false,
         % and so it needs to be special cased
G        % Push input again
n~       % Is it empty?
+        % Add thw two results. Implicit display

Python 2 , 92 71 122 Bytes

• Vielen Dank an @ovs für die starke Reduzierung um 19 Bytes &und an die |Kürzel für Set-Operationen.
• Danke @notjagan für 5 Bytes
• Danke an @ovs für 2 Bytes: set()asi-i

Lambda, das eine Liste von Mengen als Eingabe verwendet und True / False zurückgibt. Überprüft einfach, ob es eine leere Menge gibt und ob die Vereinigung und der Schnittpunkt jeder Menge (zwei Mengen, die als iund iteriert werden j) in der angegebenen Liste der Mengen vorhanden sind.

lambda x:x.sort()or all(k in x[-1]for k in range(1,max(x[-1])))and all(a in x for i in x for j in x for a in[i-j,i|j,i&j])

Probieren Sie es online!

CJam (23 Bytes)

{[,M2$2m*{_~&\~|$}/]^!}

Online-Testsuite . Dies ist ein anonymer Block (Funktion). Ich nehme an S = {0,1,...,n}; Der Block nimmt ein Array von sortierten Arrays und n+1als Parameter und verlässt 0oder 1auf dem Stapel. In dem Fall gehen {{}}der Code und das Test-Framework davon aus n+1 = 0.

Pyth, 24 23 Bytes

q@aasm,@Fd{Ssd*QQYJUEyJ

Testsuite

Dieses Programm nimmt Eingaben als geordnete Liste von geordneten Listen entgegen. Die inneren Listen müssen in aufsteigender Reihenfolge sein und die Ordnungsliste muss nach Länge und dann lexikographisch sortiert sein. Ich habe bestätigt, dass dies ein zulässiges Eingabeformat ist. Zahlen beginnen bei 0 und N + 1 wird ebenfalls als Eingabe verwendet.

Wie es funktioniert, filtern wir alles heraus, was nicht in P (S) steht, und addieren dann S, []den Schnittpunkt jedes Paares und die Vereinigung jedes Paares, deduplizieren und prüfen, ob das Ergebnis mit der Eingabe übereinstimmt.

Axiom, 358 Bytes

t(a,s)==(aa:=sort(removeDuplicates(a));ss:=sort(removeDuplicates(s));a:=sort(a);s:=sort(s);a~=aa or s~=ss=>false;a:=map(sort, a);~member?([],a) or ~member?(s,a)=>false;for x in a repeat(for j in x repeat if ~member?(j,s) then return false;for y in a repeat if ~member?(sort(setIntersection(x,y)),a) or ~member?(sort(setUnion(x,y)),a) then return false);true)

ungolfed und ergebnisse:

-- all the List have to be sorted because in list [1,2]~=[2,1]
-- So here "set" means: "List without duplicate, sorted with sort() function"
-- Return true if 
-- 1) a,s are set for above definition
-- 2) a is in P(s) 
-- 3) s,[] are in a
-- 4) for all x and y in a => xUy is in a and x intersect y is in a
t1(a:List List INT, s:List INT):Boolean==
    aa:=sort(removeDuplicates(a));ss:=sort(removeDuplicates(s))
    a :=sort(a);                  s :=sort(s)
    a~=aa          or s~=ss        =>false   -- they are not sets but list with element duplicate
    a:=map(sort, a)                          -- subset of a has to be sorted too
    ~member?([],a) or ~member?(s,a)=>false
    for x in a repeat
       for j in x repeat if ~member?(j,s) then return false 
       for y in a repeat if ~member?(sort(setIntersection(x,y)),a) or ~member?(sort(setUnion(x,y)),a) then return false
    true

(4) -> t([[]], [])
   (4)  true
                                                            Type: Boolean
(5) -> t([[],[1]], [1])
   (5)  true
                                                            Type: Boolean
(6) -> t([[],[1],[2,1]], [1,2])
   (6)  true
                                                            Type: Boolean
(7) -> t([[],[1],[2,3],[1,2,3]], [3,1,2])
   (7)  true
                                                            Type: Boolean
(8) -> t([[1], [1,2,3], [1,4,5,6], [1,2,3,4,5,6], [], [2,3], [4,5,6], [2,3,4,5,6]], [1,2,3,4,5,6])
   (8)  true
                                                            Type: Boolean
(9) -> t([[], [1], [2,3], [2], [4,5,6], [5,6], [5], [2,5,6], [2,5], [1,5], [1,2,3,4,5,6], [1,2,3], [1,2], [1,4,5,6], [1,5,6], [1,2,5,6], [2,3,4,5,6], [2,3,5,6], [2,3,5], [1,2,3,5], [2,4,5,6], [1,2,5], [1,2,3,5,6], [1,2,4,5,6]], [1,2,3,4,5,6])
   (9)  true
                                                            Type: Boolean
(10) -> t([[], [1], [1,2], [1,2,3], [1,2,3,4], [1,2,3,4,5], [1,2,3,4,5,6], [1,2,3,4,5,6,7], [1,2,3,4,5,6,7,8], [1,2,3,4,5,6,7,8,9]], [1,2,3,4,5,6,7,8,9])
   (10)  true
                                                            Type: Boolean
(11) -> t([[], [1], [1,2,3], [1,2,3,4,5], [1,2,3,4,5,6,7], [1,2,3,4,5,6,7,8,9]], [1,2,3,4,5,6,7,8,9])
   (11)  true
                                                            Type: Boolean
(2) -> t([[1]], [1])
   (2)  false
                                                            Type: Boolean
(4) -> t([[],[2]], [1,2])
   (4)  false
                                                            Type: Boolean
(5) -> t([[],[1,2],[2,3]], [1,2,3])
   (5)  false
                                                            Type: Boolean
(6) -> t([[],[1],[1,2],[2,3],[1,2,3]], [1,2,3])
   (6)  false
                                                            Type: Boolean
(7) -> t([[],[1],[2],[3],[1,2],[2,3],[1,2,3]] , [1,2,3])
   (7)  false
                                                            Type: Boolean
(8) -> t([[], [1], [2,3], [2], [4,5,6], [5,6], [5], [2,5,6], [2,5], [1,5],[1,2,3,4,5,6], [1,2,3], [1,2], [1,4,5,6], [1,5,6], [1,2,5,6], [2,3,4,5,6], [2,3,5,6], [2,3,5], [2,4,5,6], [1,2,5], [1,2,3,5,6], [1,2,4,5,6]], [1,2,3,4,5,6])
   (8)  false
                                                            Type: Boolean
(9) -> t([[], [1], [2], [1,2,3], [1,2,3,4,5], [1,2,3,4,5,6,7], [1,2,3,4,5,6,7,8,9]] , [1,2,3,4,5,6,7,8,9])
   (9)  false
                                                            Type: Boolean
(10) -> t([[], [1], [2,3], [2], [4,5,6], [5,6], [5], [2,5,6], [2,5], [1,5],[1,2,3,4,5,6], [1,2,3], [1,2], [1,4,5,6], [1,5,6], [1,2,5,6], [2,3,4,5,6], [2,3,5,6], [2,3,5], [2,4,5,6], [1,2,5], [1,2,3,5,6], [1,2,4,5,6]], [1,2,3,4,5,6])
   (10)  false
                                                            Type: Boolean