#Tatchi -- I re-worked the routines we considered today, trying to
#improve efficiency. Let me know if you have any questions.

#Script for use with Maple V release 4 
#Finds all topologies on a set and all homeomorphism types among them.
#This is nearly instantaneous when there are 2 or 3 elements in the set,
#and takes maybe 15 minutes when there are 4 elements. For 5 or more elements
#this will be painfully slow, so fortunately Maple terminates the job
#right away when it realizes that  T  has too many elements for it to
#keep track of!

#I should stress once again that
# 1. Counting the topologies on a finite set is not considered very important
# 2. It is MUCH more efficient to count homeomorphism types FIRST (using
#    more subtle couonting techniques) than to proceed this way.

with(combinat): #load in some combinatorial routines
X:={a,b,c}: #the points
Y:=powerset(X): #potential open sets
Z:=Y minus { {} , X }: #potential open sets other than the obvious ones
W:=powerset(Z): 
T:={seq(w union { {}, X }, w = W ) }: #potential topologies
print(`There are`,nops(T),`candidate collections of subsets of X!`):

istop:=proc(t) #check to see if a collection of sets is a topology
local answer, u,v,i,j:
 answer:=true:
 for i to nops(t) do u:=t[i]:
  for j to i-1 do v:=t[j]:
   if not member(u union v, t) then answer:=false:break: fi:
   if not member(u intersect v, t) then answer:=false:break: fi:
  od:
 if answer=false then break fi:
 od:
 if answer=true then t else NULL fi:
end:

Alltops:={seq(istop(t),t=T)}:
#That is now a set of all topologies on  X

print(`There are`,nops(Alltops),`topologies on a set of`,nops(X),`elements`):
#Would you like to see them? :-)
#for topo in Alltops do lprint(topo) od:

#Let's tidy them up by size:
bigger:=proc(t1,t2) if nops(t1) < nops(t2) then true else false fi:end:
#Apply this to all the elements in each topology, and to the set of all top's:
Alltops:=sort([seq( sort([op(t)],bigger) ,t=Alltops)],bigger):

#Now think about homeomorphisms, i.e., permutations preserving open sets.

P:=permute(X):
X:=[op(X)]:

newjob:=proc(t, p) local u: 
#apply a permutation p of the elements of a space to the sets in a topology t
 {seq(subs({seq(X[i]=p[i],i=1..nops(X))} ,u) , u = t)}:end:

ishomeo:=proc(t1,t2) #check to see if two spaces are homeomorphic
local answer, p:
 #we can first check for some trivial invariants, such as
  if nops(t1) <> nops(t2) then return(false) fi:
 answer:=false:
 for p in P do if {op(newjob(t1,p))}={op(t2)} then answer:=true: break: fi:od:
 #Note that we have to compare _sets_ rather than _lists_!
 answer:
end:

Types:=[]:
for t in Alltops do
 isnew:=true:
 for u in Types do 
  if ishomeo(t,u) then isnew:=false: break:fi:
 od:
 if isnew = true then Types:=[op(Types),t] fi:
od:

print(`There are`,nops(Types),`homeomorphism types of topologies among them`):

for t in Types do lprint(t) od:

#quit;
#...or keep playing with these sets...