24
\$\begingroup\$

Challenge

Given a set T of subsets of a finite set S={1,2,3,...,n}, determine whether T is a topology or not.

Explanation

The powerset P(S) of some set S is the set of all subsets of S. Some examples:

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

A topology T on the set S is a subset of P(S) with following properties:

  • {} is in T and S is in T
  • If A and B are in T then so is their intersection A ∩ B
  • If A and B are in T then so is their union A ∪ B *

* This definition is not quite correct, but it is true for finite sets, which is sufficient for the purposes of this challenge. The actual axiom would allow for infinite unions as well, but that is irrelevant in the finite case.

Details

  • You can assume that S = {1,2,...,n} (or alternatively S = {0,1,...,n}) where n is the largest integer that appears in the sets of T.
  • The input format is flexible: You can use a string, a list of lists or set of lists or any similar format your langauge can handle. You can also use sets like S = {0,1,...,n} if it is more convenient.
  • The output must be truthey or falsey.
  • You are allowed to take n (or alternatively n+1 or n-1) as an additional input.
  • If you work with ordered lists, you can assume that the numbers within a set are sorted. You can also assume that the list has a certain order (e.g. lexicographical.
  • As we represent sets, you can assume that no two entries of their list-representation are equal.

Examples

Topologies

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

non-Topologies

{{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 
\$\endgroup\$
  • 2
    \$\begingroup\$ It seems like a lot of the answers to this question would on the input {{}, {2}} because they don't explicitly check that S is in the set while for that input, S is implicitly assumed to be {1,2}. Is this a valid reading of the specs, or am I missing something? \$\endgroup\$ – Carmeister Jul 23 '17 at 19:32
  • \$\begingroup\$ @Carmeister Sorry for the confusion, yes your interpretation is correct! \$\endgroup\$ – flawr Jul 23 '17 at 19:56
  • \$\begingroup\$ Can input be a binary matrix where each row is a set, each column is an element, and the value indicates whether the element is in the set? \$\endgroup\$ – Luis Mendo Jul 23 '17 at 20:30
  • \$\begingroup\$ Yes I think that is acceptable. \$\endgroup\$ – flawr Jul 23 '17 at 20:42
  • \$\begingroup\$ Since T is a set, I think it's reasonable to assume that no subset in the input is repeated (i.e. {{}, {1,2}, {1,2}} is not valid input). Can you clarifiy that in the challenge, either affirmatively or negatively? \$\endgroup\$ – Luis Mendo Jul 23 '17 at 23:12
6
\$\begingroup\$

Python 2, 117 99 97 bytes

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

Try it online!

Output is via exit code

\$\endgroup\$
5
\$\begingroup\$

Mathematica, 87 73 66 63 bytes

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

Takes [T, n] as input.

Explanation

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

Function that returns the intersection and the union of the inputs

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

Map that function onto the input list at level 1.

... ~Flatten~2

Flatten the result (the Outer part returns a bunch of nested Lists).

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

Take the union between the flattened list and {{}, S}. This removes duplicates and adds {} and S to the resulting list.

... ==#⋃#

Check whether the list from above is equal to the sorted version of the input.

\$\endgroup\$
4
\$\begingroup\$

Haskell, 95 89 74 78 bytes

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

Try it online!

Explanation:

                              ([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
\$\endgroup\$
  • \$\begingroup\$ What about [[],[2]]? It's a topology, but not over the implied ("You can assume that...") set. \$\endgroup\$ – Christian Sievers Jul 23 '17 at 19:33
  • \$\begingroup\$ @ChristianSievers corrected! \$\endgroup\$ – flawr Jul 23 '17 at 19:58
4
\$\begingroup\$

MATL, 38 bytes

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

Input is a binary matrix where each row is a set, each column is an element, and each entry indicates membership. For example, {{},{1},{1,2}} is expressed as [0 0;1 0;1 1]. Use the linked Octave program to convert to this format.

Try it online! Or verify all test cases.

Explanation

!        % 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
\$\endgroup\$
  • 1
    \$\begingroup\$ D: your program takes up more space than your title! \$\endgroup\$ – flawr Jul 24 '17 at 13:43
3
\$\begingroup\$

Python 2, 92 71 122 bytes

  • Thanks a lot to @ovs for a heavy 19 bytes reduction: & and | shorthands for set operations.
  • Thanks @notjagan for 5 bytes
  • Thanks to @ovs for 2 bytes: set() as i-i

Lambda that takes a list of sets as input, and returns True/false. Simply checks if there is an empty set and the union and intersection of each sets(two sets iterated as i and j) exists in the given list of sets.

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

Try it online!

\$\endgroup\$
  • 1
    \$\begingroup\$ 71 bytes \$\endgroup\$ – ovs Jul 23 '17 at 19:04
  • \$\begingroup\$ @ovs Thanks a lot, didn't know the shorthands! \$\endgroup\$ – officialaimm Jul 23 '17 at 19:11
  • \$\begingroup\$ @ovs I am actually explicitly converting the list-items from the input() to set() in the footer. \$\endgroup\$ – officialaimm Jul 23 '17 at 19:11
  • 1
    \$\begingroup\$ 66 bytes. \$\endgroup\$ – notjagan Jul 23 '17 at 23:16
  • 1
    \$\begingroup\$ You can replace set() with i-i or i^i \$\endgroup\$ – ovs Jul 24 '17 at 14:05
2
\$\begingroup\$

CJam (23 bytes)

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

Online test suite. This is an anonymous block (function). I assume S = {0,1,...,n}; the block takes an array of sorted arrays and n+1 as parameters and leaves 0 or 1 on the stack. In the case {{}} the code and test framework assume that n+1 = 0.

\$\endgroup\$
2
\$\begingroup\$

Pyth, 24 23 bytes

q@aasm,@Fd{Ssd*QQYJUEyJ

Test suite

This program takes input as an ordered list of ordered lists. The inner lists must be in ascending order and the order list must be sorted by length then lexicographically. I have confirmed that this is an allowed input format. Numbers start at 0, and N+1 is also taken as input.

As for how it works, we filter out anything not in P(S), then add S, [], the intersection of every pair and the union of every pair, deduplicate, and check that the result is equal to the input.

\$\endgroup\$
0
\$\begingroup\$

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 and results:

-- 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
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.