9
\$\begingroup\$

Task

Write a function/program which takes n as a parameter/input and prints/returns the number of topologies (which is demonstrated below) on the set {1,2,...,n}.

Definition of Topology

Let X be any finite set, and assume that T, which is subset of the power set of X (i.e. a set containing subsets of X), satisfy these conditions:

  1. X and the empty set are in T.

  2. If two set U and V are in T, then the union of those two sets are in T.

  3. If two set U and V are in T, then the intersection of those two sets are in T.

...then T is called the topology on X.

Specifications

  1. Your program is either:

    • a function which takes n as a parameter
    • or a program which inputs n

    and prints or returns the number of (distinct) topologies on the set {1,2,...,n}.

  2. n is any non-negative integer which is less than 11 (of course there's no problem if your program handles n bigger than 11), and the output is a positive integer.

  3. Your program should not use any kinds of library functions or native functions which calculates the number of topology directly.

Example input (value of n) : 7

Example output/return : 9535241

You may check your return value at here or here.

Of course, shortest code wins.


The winner is decided, however, I may change the winner if shorter code appears..

\$\endgroup\$
  • \$\begingroup\$ Does it have to give results this century, or is a proof of correctness good enough? \$\endgroup\$ – Peter Taylor Jun 8 '11 at 8:30
  • \$\begingroup\$ @Peter In fact, I have no idea how long it'll take. Therefore proof of correctness of the program is good enough, but still the program should give a result in a reasonable time if n is small, like 4~5. \$\endgroup\$ – JiminP Jun 8 '11 at 8:57
  • \$\begingroup\$ @JiminP, it seems that computing it for n=12 was worth a paper back in the day, and there isn't a known formula. For 4 or 5 I suspect it's doable in a few minutes by brute force. \$\endgroup\$ – Peter Taylor Jun 8 '11 at 9:13
  • \$\begingroup\$ Is the improper subset of 2^X also a topology? \$\endgroup\$ – FUZxxl Jun 8 '11 at 21:03
  • \$\begingroup\$ @FUZxxl : Yes. I think that's called the discrete topology. \$\endgroup\$ – JiminP Jun 9 '11 at 0:50
4
\$\begingroup\$

Haskell, 144 characters

import List
import Monad
p=filterM$const[True,False]
f n=sum[1|t<-p$p[1..n],let e=(`elem`t).sort,e[],e[1..n],all e$[union,intersect]`ap`t`ap`t]

Almost a direct implementation of the specification, modulo some monad magic.

Extremely slow for n > 4.

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

Python, 147 chars

N=input()
S=lambda i,K:1+sum(0if len(set(j&k for k in K)-K)-1 else S(j+1,K|set(j|k for k in K))for j in range(i,2**N))
print S(1,set([0,2**N-1]))

Quick for N<=6, slow for N=7, unlikely N>=8 will ever complete.

Individual sets are represented by integer bitmasks, and topologies by sets of bitmasks. S(i,K) computes the number of distinct topologies you can form by starting with K and adding sets with bitmasks >= i.

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

Zsh, 83 characters

This solution matches the letter of your requirements (but not, of course, the spirit). There's undoubtedly a way to compress the numbers even more.

a=(0 3 S 9U 5CT 4HO6 5ODFS AMOZQ1 T27JJPQ 36K023FKI HW0NJPW01R);echo $[1+36#$a[$1]]
\$\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.