Calculate the number of topologies on {1,2,...,n}

Question

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

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

Answer 1

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.

Answer 2

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.

Answer 3

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

Answer 4

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

Answer 5

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

Answer 6

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