KrewerasAntichains_for_OEIS.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "9aa8f1ef",
   "metadata": {},
   "source": [
    "# Counting (maximal) antichains in Kreweras lattice of non-crossing set partitions\n",
    "\n",
    "\n",
    "This is a supporing file for OEIS on computation of (maximal) antichains in the Kreweras lattice of non-crossing set partitions.\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 Kreweras 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": [
    "import numpy as np\n",
    "\n",
    "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",
    "        #вычисление признакового замыкания\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",
    "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",
    "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",
    "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",
    "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"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c23f0663",
   "metadata": {},
   "source": [
    "### 1. Loading formal contexts for antichains and maximal antichains of a partition lattice"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "ed215b87",
   "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",
      "01101\n",
      "\n",
      "00000\n",
      "\n",
      "B\n",
      "\n",
      "\n",
      "\n",
      "\n",
      "\n",
      "01111111111111\n",
      "\n",
      "00111111111111\n",
      "\n",
      "01011111111111\n",
      "\n",
      "01101111111111\n",
      "\n",
      "00000111111111\n",
      "\n",
      "01111011111111\n",
      "\n",
      "01101001111111\n",
      "\n",
      "01111110111111\n",
      "\n",
      "00111010011111\n",
      "\n",
      "01111111101111\n",
      "\n",
      "00111111100111\n",
      "\n",
      "01011011101011\n",
      "\n",
      "01101110101101\n",
      "\n",
      "00000000000000\n",
      "\n",
      "B\n",
      "\n",
      "\n",
      "\n",
      "\n",
      "\n",
      "011111111111111111111111111111111111111111\n",
      "\n",
      "001111111111111111111111111111111111111111\n",
      "\n",
      "010111111111111111111111111111111111111111\n",
      "\n",
      "011011111111111111111111111111111111111111\n",
      "\n",
      "000001111111111111111111111111111111111111\n",
      "\n",
      "011110111111111111111111111111111111111111\n",
      "\n",
      "011010011111111111111111111111111111111111\n",
      "\n",
      "011111101111111111111111111111111111111111\n",
      "\n",
      "001110100111111111111111111111111111111111\n",
      "\n",
      "011111111011111111111111111111111111111111\n",
      "\n",
      "001111111001111111111111111111111111111111\n",
      "\n",
      "010110111010111111111111111111111111111111\n",
      "\n",
      "011011101011011111111111111111111111111111\n",
      "\n",
      "000000000000001111111111111111111111111111\n",
      "\n",
      "011111111111110111111111111111111111111111\n",
      "\n",
      "011011111111110011111111111111111111111111\n",
      "\n",
      "011111101111110101111111111111111111111111\n",
      "\n",
      "011111111011110110111111111111111111111111\n",
      "\n",
      "011011101011010000011111111111111111111111\n",
      "\n",
      "011111111111111111101111111111111111111111\n",
      "\n",
      "011111111011111111100111111111111111111111\n",
      "\n",
      "001111111111110111101011111111111111111111\n",
      "\n",
      "001111111001110110100001111111111111111111\n",
      "\n",
      "011111111111111111111110111111111111111111\n",
      "\n",
      "001111111111111111111110011111111111111111\n",
      "\n",
      "010111111111110111111110101111111111111111\n",
      "\n",
      "011011111111111111101110110111111111111111\n",
      "\n",
      "000001111111110011101010000011111111111111\n",
      "\n",
      "011111111111111111111111111101111111111111\n",
      "\n",
      "001111111111111111111111111100111111111111\n",
      "\n",
      "010111111111111111111111111101011111111111\n",
      "\n",
      "011011111111111111111111111101101111111111\n",
      "\n",
      "000001111111111111111111111100000111111111\n",
      "\n",
      "011110111111110111111111111101111011111111\n",
      "\n",
      "011010011111110011111111111101101001111111\n",
      "\n",
      "011111101111111111101111111101111110111111\n",
      "\n",
      "001110100111110101101011111100111010011111\n",
      "\n",
      "011111111011111111111110111101111111101111\n",
      "\n",
      "001111111001111111111110011100111111100111\n",
      "\n",
      "010110111010110110111110101101011011101011\n",
      "\n",
      "011011101011011111100110110101101110101101\n",
      "\n",
      "000000000000000000000000000000000000000000\n",
      "\n"
     ]
    }
   ],
   "source": [
    "AC_cxts=[cxtFromFile(\"AC_Kreweras\"+str(n)+\".cxt\") for n in range(6)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "db4d6218",
   "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",
      "01111\n",
      "\n",
      "00001\n",
      "\n",
      "B\n",
      "\n",
      "\n",
      "\n",
      "\n",
      "\n",
      "11111111111111\n",
      "\n",
      "01111111111111\n",
      "\n",
      "01111111111111\n",
      "\n",
      "01111111111111\n",
      "\n",
      "00001111111111\n",
      "\n",
      "01111111111111\n",
      "\n",
      "01101011111111\n",
      "\n",
      "01111111111111\n",
      "\n",
      "00111010111111\n",
      "\n",
      "01111111111111\n",
      "\n",
      "00111111101111\n",
      "\n",
      "01011011101111\n",
      "\n",
      "01101110101111\n",
      "\n",
      "00000000000001\n",
      "\n",
      "B\n",
      "\n",
      "\n",
      "\n",
      "\n",
      "\n",
      "111111111111111111111111111111111111111111\n",
      "\n",
      "011111111111111111111111111111111111111111\n",
      "\n",
      "011111111111111111111111111111111111111111\n",
      "\n",
      "011111111111111111111111111111111111111111\n",
      "\n",
      "000011111111111111111111111111111111111111\n",
      "\n",
      "011111111111111111111111111111111111111111\n",
      "\n",
      "011010111111111111111111111111111111111111\n",
      "\n",
      "011111111111111111111111111111111111111111\n",
      "\n",
      "001110101111111111111111111111111111111111\n",
      "\n",
      "011111111111111111111111111111111111111111\n",
      "\n",
      "001111111011111111111111111111111111111111\n",
      "\n",
      "010110111011111111111111111111111111111111\n",
      "\n",
      "011011101011111111111111111111111111111111\n",
      "\n",
      "000000000000011111111111111111111111111111\n",
      "\n",
      "011111111111111111111111111111111111111111\n",
      "\n",
      "011011111111110111111111111111111111111111\n",
      "\n",
      "011111101111110111111111111111111111111111\n",
      "\n",
      "011111111011110111111111111111111111111111\n",
      "\n",
      "011011101011010000111111111111111111111111\n",
      "\n",
      "011111111111111111111111111111111111111111\n",
      "\n",
      "011111111011111111101111111111111111111111\n",
      "\n",
      "001111111111110111101111111111111111111111\n",
      "\n",
      "001111111001110110100011111111111111111111\n",
      "\n",
      "011111111111111111111111111111111111111111\n",
      "\n",
      "001111111111111111111110111111111111111111\n",
      "\n",
      "010111111111110111111110111111111111111111\n",
      "\n",
      "011011111111111111101110111111111111111111\n",
      "\n",
      "000001111111110011101010000111111111111111\n",
      "\n",
      "011111111111111111111111111111111111111111\n",
      "\n",
      "001111111111111111111111111101111111111111\n",
      "\n",
      "010111111111111111111111111101111111111111\n",
      "\n",
      "011011111111111111111111111101111111111111\n",
      "\n",
      "000001111111111111111111111100001111111111\n",
      "\n",
      "011110111111110111111111111101111111111111\n",
      "\n",
      "011010011111110011111111111101101011111111\n",
      "\n",
      "011111101111111111101111111101111111111111\n",
      "\n",
      "001110100111110101101011111100111010111111\n",
      "\n",
      "011111111011111111111110111101111111111111\n",
      "\n",
      "001111111001111111111110011100111111101111\n",
      "\n",
      "010110111010110110111110101101011011101111\n",
      "\n",
      "011011101011011111100110110101101110101111\n",
      "\n",
      "000000000000000000000000000000000000000001\n",
      "\n"
     ]
    }
   ],
   "source": [
    "MA_cxts=[cxtFromFile(\"MA_Kreweras\"+str(n)+\".cxt\") for n in range(6)]"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "271cf201",
   "metadata": {},
   "source": [
    "### 2. Generation of maximal antichains for n in {0,1,2,3,4,5} "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "2f7e88de",
   "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 164 ms, sys: 3.54 ms, total: 167 ms\n",
      "Wall time: 166 ms\n"
     ]
    }
   ],
   "source": [
    "%%time\n",
    "MAs=[CountAllClosures(c) for c in  MA_cxts[:6]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "971661a5",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 1, 2, 3, 25, 2117]"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "MAs"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "401257f3",
   "metadata": {},
   "source": [
    "### 3. Counting of  antichains for n in {0, 1, 2, 3, 4, 5}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "d5d4fc9d",
   "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",
      "1000000\n",
      "2000000\n",
      "Branch terminated with -1\n",
      "CPU times: user 2min 28s, sys: 552 ms, total: 2min 29s\n",
      "Wall time: 2min 55s\n"
     ]
    }
   ],
   "source": [
    "%%time\n",
    "ACs=[CountAllClosures(c) for c in  AC_cxts[:6]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "350c1316",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[2, 2, 3, 10, 234, 2342196]"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "ACs"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "7f988b6f",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "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
}