25
4
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 inT
andS
is inT
- If
A
andB
are inT
then so is their intersectionA ∩ B
- If
A
andB
are inT
then so is their unionA ∪ 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 alternativelyS = {0,1,...,n}
) wheren
is the largest integer that appears in the sets ofT
. - 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 alternativelyn+1
orn-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
2It 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? – Carmeister – 2017-07-23T19:32:20.707
@Carmeister Sorry for the confusion, yes your interpretation is correct! – flawr – 2017-07-23T19:56:05.227
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? – Luis Mendo – 2017-07-23T20:30:31.050
Yes I think that is acceptable. – flawr – 2017-07-23T20:42:34.750
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? – Luis Mendo – 2017-07-23T23:12:53.373I'm using an ordered list as input. May I assume a specific ordering on the input list (the overall list)? – isaacg – 2017-07-24T10:45:28.187
If I choose to work on the assumption that
S = {0,1,...,n}
and to taken+1
as an additional input, what value will be supplied as the additional input for the first test case?0
? – Peter Taylor – 2017-07-24T11:07:27.187@PeterTaylor I think
-1
would be reasonable, in order to produce an empty base setS
. But I see that this might be cumbersome, so I think it is ok to ignore this pathological case and assume that|S|>0
– flawr – 2017-07-24T13:36:04.963@isaacg Yes that should be ok! – flawr – 2017-07-24T13:36:18.737
@LuisMendo Yes you can assume that you do not get the same element of a set twice in its representation. – flawr – 2017-07-24T13:40:23.650