13
\$\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 \$\emptyset\$ are in \$T\$.

  2. If \$U, V\$ are in \$T\$, then the union of those two sets is in \$T\$.

  3. If \$U, V\$ are in \$T\$, then the intersection of those two sets is 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\}\$.

  1. \$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.

  2. 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\$
7
  • \$\begingroup\$ Does it have to give results this century, or is a proof of correctness good enough? \$\endgroup\$ Commented Jun 8, 2011 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
    Commented Jun 8, 2011 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\$ Commented Jun 8, 2011 at 9:13
  • \$\begingroup\$ Is the improper subset of 2^X also a topology? \$\endgroup\$
    – FUZxxl
    Commented Jun 8, 2011 at 21:03
  • \$\begingroup\$ @FUZxxl : Yes. I think that's called the discrete topology. \$\endgroup\$
    – JiminP
    Commented Jun 9, 2011 at 0:50

6 Answers 6

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\$
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\$
1
\$\begingroup\$

Python, 131 chars

lambda n:sum(x&(x>>2**n-1)&all((~(x>>i&x>>j)|x>>(i|j)&x>>(i&j))&1 for i in range(2**n)for j in range(2**n))for x in range(2**2**n))

Expanded version:

def f(n):
    count = 0
    for x in range(2**2**n): # for every set x of subsets of [n] = {1,...,n}
        try:
            assert x & 1 # {} is in x
            assert (x >> 2 ** n - 1) & 1 # [n] is in x
            for i in range(2**n): # for every subset i of [n]...
                if x >> i & 1: # ...in x
                    for j in range(2**n): # for every subset j of [n]...
                        if x >> j & 1: # ...in x
                            assert (x >> (i | j)) & 1 # their union is in x
                            assert (x >> (i & j)) & 1 # their intersection is in x
            count += 1
        except AssertionError:
            pass
    return count

For example, suppose n = 3. The possible subsets of [n] are

0b000
0b001
0b010
0b011
0b100
0b101
0b110
0b111

where the ith bit indicates whether i is in the subset. To encode sets of subsets, we notice that each of these subsets either belongs or does not belong to the set in question. Thus, for example,

x = 0b10100001
0b000 # 1
0b001 # 0
0b010 # 1
0b011 # 0
0b100 # 0
0b101 # 0
0b110 # 0
0b111 # 1

indicates that x contains {}, {2}, and {1,2,3}.

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

Jelly, 28 bytes

ŒP⁺f,œ|ɗþ`ẎẎṢe¥€Ʋ;ẠCaiʋẠʋ€RS

Try it online!

So, incredibly, slow. Times out on TIO for all \$n \ge 4\$, and running it locally with \$n = 4\$ still didn't produce an output after 15 minutes. That is because this answer has a time complexity of \$O(2^{2^n})\$, as we calculate \$\mathcal P(\mathcal P(\{1, 2, ..., n\}))\$ and filter on topologies.

How it works

ŒP⁺f,œ|ɗþ`ẎẎṢe¥€Ʋ;ẠCaiʋẠʋ€RS - Main link. Takes n on the left
ŒP                           - Powerset of X = [1, 2, ..., n]
  ⁺                          - Powerset of that
                        ʋ    - Last 4 links as a dyad f(T, X):
                Ʋ            -   Last 4 links as a monad g(T):
       ɗ                     -     Last 3 links as a dyad h(U, V):
   f                         -       U ∩ V
     œ|                      -       U ∪ V
    ,                        -       [U ∩ V, U ∪ V]
        þ`                   -     For all U ∈ T, V ∈ T, calculate h(U, V)
          ẎẎ                 -     Flatten into a list of unions and intersections
              ¥              -     Last 2 links as a dyad k(Z, T):
            Ṣ                -       Sort Z
             e               -       Is Z ∈ T?
               €             -     For each Z in the list of unions and intersections, find k(Z, T)
                      ʋ      -   Last 4 links as a dyad l(T, X):
                  Ạ          -     Are all elements of T truthy?
                   C         -     Complement; are any falsey?
                     i       -     Index of X in T, or 0 if not present
                    a        -     And; are both true?
                 ;           -   Concatenate the list of k(Z, T)s with l(T, X)
                       Ạ     -   Are all true?
                          R  - X = [1, 2, ..., n]
                         €   - Over each T ∈ P(P(X)), calculate f(T, X)
                           S - Count the truthy elements
\$\endgroup\$
0
\$\begingroup\$

Scala, 450 343 bytes

Thanks to the comment, saved 107 bytes using some trivial tricks.


rewrite @user76284's solution into scala.

Using scala for calculation is so slow! On TIO, I only use one case f(4)=355


Golfed version. Try it online!

def f(n:Int)={var c=0;for(x<-0 until math.pow(2,math.pow(2,n)).toInt){try{assert((x&1)!=0);assert((x>>((math.pow(2,n)-1).toInt)&1)!=0);for(i<-0 until math.pow(2,n).toInt){if(((x>>i)&1)!=0){for(j<-0 until math.pow(2,n).toInt){if(((x>>j)&1)!=0){assert(((x>>(i|j))&1)!=0);assert(((x>>(i&j))&1)!= 0);}}}}; c+=1;}catch{case _:AssertionError=>;}};c}

Ungoled version. Try it online!

object Main {
  def f(n: Int): Int = {
    var count = 0
    for (x <- 0 until math.pow(2, math.pow(2, n)).toInt) {
      try {
        assert((x & 1) != 0)
        assert((x >> ((math.pow(2, n) - 1).toInt) & 1) != 0)
        for (i <- 0 until math.pow(2, n).toInt) {
          if ( ((x >> i) & 1) != 0) {
            for (j <- 0 until math.pow(2, n).toInt) {
              if ( ((x >> j) & 1) != 0) {
                assert( ((x >> (i | j)) & 1) != 0)
                assert( ((x >> (i & j)) & 1) != 0)
              }
            }
          }
        }
        count += 1
      } catch {
        case _: AssertionError =>
      }
    }
    count
  }

  def main(args: Array[String]): Unit = {
    val n =4
    val result = f(n)
    println(s"f($n) = $result")
  }
}

\$\endgroup\$
1
  • 1
    \$\begingroup\$ Can you remove a lot of the spaces, and use single character variables names (e.g. c instead of count) to save a bunch of bytes? \$\endgroup\$ Commented Apr 20, 2023 at 15:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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