TamariLatticeACs_for_OEIS.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "698378aa",
   "metadata": {},
   "source": [
    "# Counting (maximal) antichains in the Tamari lattice of order n\n",
    "\n",
    "\n",
    "This is a supporing file for OEIS on computation of (maximal) antichains in the Tamari lattice of order n.\n",
    "\n",
    "## Outline\n",
    "\n",
    "### 0. The basic code with the class for managing generation of formal concepts via NextClosure algorithm\n",
    "\n",
    "### 1. Loading formal contexts for antichains and maximal antichains of Tamari lattice\n",
    "\n",
    "### 2. Counting of maximal antichains for n in {0, 1, 2, 3, 4, 5} \n",
    "\n",
    "### 3. Counting of  antichains for n in {0, 1, 2, 3, 4, 5} "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "58e6429c",
   "metadata": {},
   "outputs": [],
   "source": [
    "class nnBitContext:\n",
    "    def __init__(self, n=3, i=0, m=3):\n",
    "            self.attr_names=[str(k+1) for k in range(n)]\n",
    "            self.objects=[]\n",
    "            self.obj_names=[str(k+1) for k in range(m)]\n",
    "            #print(bin(i))\n",
    "            for j in range(m):                \n",
    "                self.objects.append(i & ((1<<n) - 1))\n",
    "                #print(bin(i & ((1<<n) - 1)))\n",
    "                i=i<<1\n",
    "                #print(bin(i))\n",
    "            self.nAttr=len(self.attr_names)\n",
    "            self.nObj=len(self.objects)\n",
    "            self.name=\"Context\"\n",
    "\n",
    "      \n",
    " \n",
    "    def aClosure(self,aSet):\n",
    "        #computing attribute closure\n",
    "        B=(1<<self.nAttr)-1\n",
    "        for g in self.objects:\n",
    "            if aSet & g == aSet:\n",
    "                B=B & g        \n",
    "        return B\n",
    "    \n",
    "   \n",
    "    \n",
    "def cxtFromFile(filename):\n",
    "    cxt=nnBitContext(0,0,0)\n",
    "   \n",
    "    f = open(filename, \"r\")\n",
    "    print(f.readline())\n",
    "    print(f.readline())\n",
    "        \n",
    "    cxt.nObj=int(f.readline())\n",
    "    cxt.nAttr=int(f.readline())\n",
    "    \n",
    "    print(f.readline())\n",
    "    \n",
    "    for i in range(cxt.nObj):\n",
    "        cxt.obj_names.append(f.readline())\n",
    "    \n",
    "    for i in range(cxt.nAttr):\n",
    "        cxt.attr_names.append(f.readline())\n",
    "    \n",
    "\n",
    "    for l in range(cxt.nObj):\n",
    "        o=f.readline().replace('.','0').replace('x','1')\n",
    "        print(o)\n",
    "        \n",
    "        cxt.objects.append(int(o,2))\n",
    "        #print(bin(i & ((1<<n) - 1)))\n",
    "        \n",
    "        #print(bin(i)\n",
    "    cxt.name=filename[:-4]\n",
    "    f.close()\n",
    "    return cxt  \n",
    "\n",
    "\n",
    "    \n",
    "    \n",
    "    \n",
    "    \n",
    "def BitNextClosure(A,bCxt):\n",
    "    #print(\"Bit NextClosure\")\n",
    "    for m in range(bCxt.nAttr-1,-1,-1):\n",
    "        #print(\"m=\",m)\n",
    "        if A & (1<<m):\n",
    "            #print(\"A=\",A)\n",
    "            A= A & ~(1<<m)\n",
    "            #print(\"A= A & ~(1<<m)\",A)\n",
    "        else:\n",
    "            B=bCxt.aClosure(A |(1<<m))\n",
    "            #print(\"A=\",A,bin(A))\n",
    "            #print(\"B=cl(AUm)\",B)\n",
    "            B_A=B & ~A\n",
    "            #print(\"B-A\",B_A,bin(B_A))\n",
    "            if not B_A & ((1<<m)-1):\n",
    "                #print(\"B_A\", B_A, bin(B_A), \"((1<<m)-1)\", ((1<<m)-1), bin(((1<<m)-1)))  \n",
    "                return B\n",
    "    print(\"Branch terminated with -1\")\n",
    "    return -1  \n",
    "    \n",
    "    \n",
    "    \n",
    "\n",
    "def FirstClosure(bCxt):\n",
    "    #print(\"First closure\")\n",
    "    if bCxt.objects==[]:\n",
    "        return 2**bCxt.nAttr-1\n",
    "    eCl=bCxt.objects[0]\n",
    "    if eCl:\n",
    "        for g in bCxt.objects[1:]:\n",
    "            eCl= eCl & g \n",
    "  \n",
    "    return eCl\n",
    "\n",
    "\n",
    "\n",
    "def CountAllClosures(bCxt):\n",
    "    \n",
    "    #print(\"All closures\")\n",
    "    cnt=0\n",
    "    prevcnt=0\n",
    "    A=FirstClosure(bCxt)\n",
    "    #print(\"First Closure\",A,bin(A))\n",
    "    while A!=-1:\n",
    "        #print (\"A=\",A, \"binary representation\", bin(A))\n",
    "        cnt+=1\n",
    "        A=BitNextClosure(A,bCxt)\n",
    "        if cnt%1000000==0: \n",
    "            if cnt!=prevcnt: \n",
    "                print(cnt)\n",
    "                prevcnt=cnt\n",
    "    return cnt\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f04d0db3",
   "metadata": {},
   "source": [
    "### 1. Loading formal contexts for antichains and maximal antichains of a partition lattice"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "75afdcae",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "B\n",
      "\n",
      "\n",
      "\n",
      "\n",
      "\n",
      "0\n",
      "\n",
      "B\n",
      "\n",
      "\n",
      "\n",
      "\n",
      "\n",
      "0\n",
      "\n",
      "B\n",
      "\n",
      "\n",
      "\n",
      "\n",
      "\n",
      "01\n",
      "\n",
      "00\n",
      "\n",
      "B\n",
      "\n",
      "\n",
      "\n",
      "\n",
      "\n",
      "01111\n",
      "\n",
      "00111\n",
      "\n",
      "01011\n",
      "\n",
      "01001\n",
      "\n",
      "00000\n",
      "\n",
      "B\n",
      "\n",
      "\n",
      "\n",
      "\n",
      "\n",
      "01111111111111\n",
      "\n",
      "00111111111111\n",
      "\n",
      "01011111111111\n",
      "\n",
      "01001111111111\n",
      "\n",
      "00000111111111\n",
      "\n",
      "01111011111111\n",
      "\n",
      "00111001111111\n",
      "\n",
      "01111010111111\n",
      "\n",
      "01111010011111\n",
      "\n",
      "00111000001111\n",
      "\n",
      "01011010110111\n",
      "\n",
      "01011010010011\n",
      "\n",
      "01001010010001\n",
      "\n",
      "00000000000000\n",
      "\n",
      "B\n",
      "\n",
      "\n",
      "\n",
      "\n",
      "\n",
      "011111111111111111111111111111111111111111\n",
      "\n",
      "001111111111111111111111111111111111111111\n",
      "\n",
      "010111111111111111111111111111111111111111\n",
      "\n",
      "010011111111111111111111111111111111111111\n",
      "\n",
      "000001111111111111111111111111111111111111\n",
      "\n",
      "011110111111111111111111111111111111111111\n",
      "\n",
      "001110011111111111111111111111111111111111\n",
      "\n",
      "011110101111111111111111111111111111111111\n",
      "\n",
      "011110100111111111111111111111111111111111\n",
      "\n",
      "001110000011111111111111111111111111111111\n",
      "\n",
      "010110101101111111111111111111111111111111\n",
      "\n",
      "010110100100111111111111111111111111111111\n",
      "\n",
      "010010100100011111111111111111111111111111\n",
      "\n",
      "000000000000001111111111111111111111111111\n",
      "\n",
      "011111111111110111111111111111111111111111\n",
      "\n",
      "001111111111110011111111111111111111111111\n",
      "\n",
      "010111111111110101111111111111111111111111\n",
      "\n",
      "010011111111110100111111111111111111111111\n",
      "\n",
      "000001111111110000011111111111111111111111\n",
      "\n",
      "011111111111110111101111111111111111111111\n",
      "\n",
      "001111111111110011100111111111111111111111\n",
      "\n",
      "011111111111110111101011111111111111111111\n",
      "\n",
      "011111111111110111101001111111111111111111\n",
      "\n",
      "001111111111110011100000111111111111111111\n",
      "\n",
      "010111111111110101101011011111111111111111\n",
      "\n",
      "010111111111110101101001001111111111111111\n",
      "\n",
      "010011111111110100101001000111111111111111\n",
      "\n",
      "000001111111110000000000000011111111111111\n",
      "\n",
      "011110111111110111101111111101111111111111\n",
      "\n",
      "001110011111110011100111111100111111111111\n",
      "\n",
      "011110111111110111101011111101011111111111\n",
      "\n",
      "011110111111110111101001111101001111111111\n",
      "\n",
      "001110011111110011100000111100000111111111\n",
      "\n",
      "011110101111110111101011111101011011111111\n",
      "\n",
      "011110101111110111101001111101001001111111\n",
      "\n",
      "011110100111110111101001111101001000111111\n",
      "\n",
      "001110000011110011100000111100000000011111\n",
      "\n",
      "010110101101110101101011011101011011101111\n",
      "\n",
      "010110101101110101101001001101001001100111\n",
      "\n",
      "010110100100110101101001001101001000100011\n",
      "\n",
      "010010100100010100101001000101001000100001\n",
      "\n",
      "000000000000000000000000000000000000000000\n",
      "\n"
     ]
    }
   ],
   "source": [
    "AC_cxts=[cxtFromFile(\"AC_Tamari\"+str(i)+\".cxt\") for i in range(6)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "b5b9fe5f",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "B\n",
      "\n",
      "\n",
      "\n",
      "\n",
      "\n",
      "1\n",
      "\n",
      "B\n",
      "\n",
      "\n",
      "\n",
      "\n",
      "\n",
      "1\n",
      "\n",
      "B\n",
      "\n",
      "\n",
      "\n",
      "\n",
      "\n",
      "11\n",
      "\n",
      "01\n",
      "\n",
      "B\n",
      "\n",
      "\n",
      "\n",
      "\n",
      "\n",
      "11111\n",
      "\n",
      "01111\n",
      "\n",
      "01111\n",
      "\n",
      "01011\n",
      "\n",
      "00001\n",
      "\n",
      "B\n",
      "\n",
      "\n",
      "\n",
      "\n",
      "\n",
      "11111111111111\n",
      "\n",
      "01111111111111\n",
      "\n",
      "01111111111111\n",
      "\n",
      "01011111111111\n",
      "\n",
      "00001111111111\n",
      "\n",
      "01111111111111\n",
      "\n",
      "00111011111111\n",
      "\n",
      "01111011111111\n",
      "\n",
      "01111010111111\n",
      "\n",
      "00111000011111\n",
      "\n",
      "01011010111111\n",
      "\n",
      "01011010010111\n",
      "\n",
      "01001010010011\n",
      "\n",
      "00000000000001\n",
      "\n",
      "B\n",
      "\n",
      "\n",
      "\n",
      "\n",
      "\n",
      "111111111111111111111111111111111111111111\n",
      "\n",
      "011111111111111111111111111111111111111111\n",
      "\n",
      "011111111111111111111111111111111111111111\n",
      "\n",
      "010111111111111111111111111111111111111111\n",
      "\n",
      "000011111111111111111111111111111111111111\n",
      "\n",
      "011111111111111111111111111111111111111111\n",
      "\n",
      "001110111111111111111111111111111111111111\n",
      "\n",
      "011110111111111111111111111111111111111111\n",
      "\n",
      "011110101111111111111111111111111111111111\n",
      "\n",
      "001110000111111111111111111111111111111111\n",
      "\n",
      "010110101111111111111111111111111111111111\n",
      "\n",
      "010110100101111111111111111111111111111111\n",
      "\n",
      "010010100100111111111111111111111111111111\n",
      "\n",
      "000000000000011111111111111111111111111111\n",
      "\n",
      "011111111111111111111111111111111111111111\n",
      "\n",
      "001111111111110111111111111111111111111111\n",
      "\n",
      "010111111111110111111111111111111111111111\n",
      "\n",
      "010011111111110101111111111111111111111111\n",
      "\n",
      "000001111111110000111111111111111111111111\n",
      "\n",
      "011111111111110111111111111111111111111111\n",
      "\n",
      "001111111111110011101111111111111111111111\n",
      "\n",
      "011111111111110111101111111111111111111111\n",
      "\n",
      "011111111111110111101011111111111111111111\n",
      "\n",
      "001111111111110011100001111111111111111111\n",
      "\n",
      "010111111111110101101011111111111111111111\n",
      "\n",
      "010111111111110101101001011111111111111111\n",
      "\n",
      "010011111111110100101001001111111111111111\n",
      "\n",
      "000001111111110000000000000111111111111111\n",
      "\n",
      "011110111111110111101111111111111111111111\n",
      "\n",
      "001110011111110011100111111101111111111111\n",
      "\n",
      "011110111111110111101011111101111111111111\n",
      "\n",
      "011110111111110111101001111101011111111111\n",
      "\n",
      "001110011111110011100000111100001111111111\n",
      "\n",
      "011110101111110111101011111101011111111111\n",
      "\n",
      "011110101111110111101001111101001011111111\n",
      "\n",
      "011110100111110111101001111101001001111111\n",
      "\n",
      "001110000011110011100000111100000000111111\n",
      "\n",
      "010110101101110101101011011101011011111111\n",
      "\n",
      "010110101101110101101001001101001001101111\n",
      "\n",
      "010110100100110101101001001101001000100111\n",
      "\n",
      "010010100100010100101001000101001000100011\n",
      "\n",
      "000000000000000000000000000000000000000001\n",
      "\n"
     ]
    }
   ],
   "source": [
    "MA_cxts=[cxtFromFile(\"MA_Tamari\"+str(i)+\".cxt\") for i in range(6)]"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d70b4983",
   "metadata": {},
   "source": [
    "### 2. Generation of maximal antichains for n in {0,1,2,3,4,5} "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "0a902f96",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Branch terminated with -1\n",
      "Branch terminated with -1\n",
      "Branch terminated with -1\n",
      "Branch terminated with -1\n",
      "Branch terminated with -1\n",
      "Branch terminated with -1\n",
      "CPU times: user 55.4 ms, sys: 1.88 ms, total: 57.2 ms\n",
      "Wall time: 57 ms\n"
     ]
    }
   ],
   "source": [
    "%%time\n",
    "MAs=[CountAllClosures(c) for c in  MA_cxts]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "35f61471",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 1, 2, 4, 26, 1979]"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "MAs"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8073d463",
   "metadata": {},
   "source": [
    "### 3. Counting of  antichains for n in {0, 1, 2, 3, 4, 5}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "257e9b9a",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Branch terminated with -1\n",
      "Branch terminated with -1\n",
      "Branch terminated with -1\n",
      "Branch terminated with -1\n",
      "Branch terminated with -1\n",
      "Branch terminated with -1\n",
      "CPU times: user 627 ms, sys: 5.12 ms, total: 633 ms\n",
      "Wall time: 633 ms\n"
     ]
    }
   ],
   "source": [
    "%%time\n",
    "ACs=[CountAllClosures(c) for c in  AC_cxts]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "22b05fa8",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[2, 2, 3, 8, 83, 28984]"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "ACs"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.8"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}