SetPartAntichains_for_OEIS.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "8a238c2f",
   "metadata": {},
   "source": [
    "# Counting (maximal) antichains in the lattice of set partitions\n",
    "\n",
    "\n",
    "This is a supporing file for OEIS on computation of (maximal) antichains in the lattice of 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 a partition 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}  (https://oeis.org/A302250)\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "fd1c2671",
   "metadata": {},
   "source": [
    "### 0. The basic code with the class for managing generation of formal concepts via NextClosure algorithm"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "eca1a1d6",
   "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",
    "    \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",
    "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",
    "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": "f079f211",
   "metadata": {},
   "source": [
    "### 1. Loading formal contexts for antichains and maximal antichains of a partition lattice"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "c2b2c60c",
   "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",
      "011111111111111\n",
      "\n",
      "001111111111111\n",
      "\n",
      "010111111111111\n",
      "\n",
      "011011111111111\n",
      "\n",
      "000001111111111\n",
      "\n",
      "011110111111111\n",
      "\n",
      "011111011111111\n",
      "\n",
      "001110001111111\n",
      "\n",
      "011111110111111\n",
      "\n",
      "011010110011111\n",
      "\n",
      "011111111101111\n",
      "\n",
      "010110111100111\n",
      "\n",
      "011011011101011\n",
      "\n",
      "001111110101101\n",
      "\n",
      "000000000000000\n",
      "\n",
      "B\n",
      "\n",
      "\n",
      "\n",
      "\n",
      "\n",
      "0111111111111111111111111111111111111111111111111111\n",
      "\n",
      "0011111111111111111111111111111111111111111111111111\n",
      "\n",
      "0101111111111111111111111111111111111111111111111111\n",
      "\n",
      "0110111111111111111111111111111111111111111111111111\n",
      "\n",
      "0000011111111111111111111111111111111111111111111111\n",
      "\n",
      "0111101111111111111111111111111111111111111111111111\n",
      "\n",
      "0111110111111111111111111111111111111111111111111111\n",
      "\n",
      "0011100011111111111111111111111111111111111111111111\n",
      "\n",
      "0111111101111111111111111111111111111111111111111111\n",
      "\n",
      "0110101100111111111111111111111111111111111111111111\n",
      "\n",
      "0111111111011111111111111111111111111111111111111111\n",
      "\n",
      "0101101111001111111111111111111111111111111111111111\n",
      "\n",
      "0110110111010111111111111111111111111111111111111111\n",
      "\n",
      "0011111101011011111111111111111111111111111111111111\n",
      "\n",
      "0000000000000001111111111111111111111111111111111111\n",
      "\n",
      "0111111111111110111111111111111111111111111111111111\n",
      "\n",
      "0111111111111111011111111111111111111111111111111111\n",
      "\n",
      "0011111111111110001111111111111111111111111111111111\n",
      "\n",
      "0111111111111111110111111111111111111111111111111111\n",
      "\n",
      "0110111111111110110011111111111111111111111111111111\n",
      "\n",
      "0111111111111111111101111111111111111111111111111111\n",
      "\n",
      "0101111111111110111100111111111111111111111111111111\n",
      "\n",
      "0110111111111111011101011111111111111111111111111111\n",
      "\n",
      "0011111111111111110101101111111111111111111111111111\n",
      "\n",
      "0000011111111110000000000111111111111111111111111111\n",
      "\n",
      "0111111111111111111111111011111111111111111111111111\n",
      "\n",
      "0111111111011110111111111001111111111111111111111111\n",
      "\n",
      "0111111111111111111111111110111111111111111111111111\n",
      "\n",
      "0111111101111110111111111110011111111111111111111111\n",
      "\n",
      "0111111111011111011111111110101111111111111111111111\n",
      "\n",
      "0011111111111111111111111010110111111111111111111111\n",
      "\n",
      "0011111101011010001111111000000011111111111111111111\n",
      "\n",
      "0111111111111111111111111111111101111111111111111111\n",
      "\n",
      "0111110111111110111111111111111100111111111111111111\n",
      "\n",
      "0111111111011111110111111111111101011111111111111111\n",
      "\n",
      "0110111111111111111111111011111101101111111111111111\n",
      "\n",
      "0110110111010110110011111001111100000111111111111111\n",
      "\n",
      "0111111111111111111111111111111111111011111111111111\n",
      "\n",
      "0111101111111110111111111111111111111001111111111111\n",
      "\n",
      "0111110111111111011111111111111111111010111111111111\n",
      "\n",
      "0111111101111111110111111111111111111011011111111111\n",
      "\n",
      "0111111111011111111101111111111111111011101111111111\n",
      "\n",
      "0101111111111111111111111011111111111011110111111111\n",
      "\n",
      "0101101111001110111100111001111111111001100011111111\n",
      "\n",
      "0110111111111111111111111110111111111011111101111111\n",
      "\n",
      "0110101100111110110011111110011111111001011100111111\n",
      "\n",
      "0110110111010111011101011110101111111010101101011111\n",
      "\n",
      "0011111111111111111111111111111101111011111111101111\n",
      "\n",
      "0011100011111110001111111111111100111000111111100111\n",
      "\n",
      "0011111101011011110101101111111101011011001111101011\n",
      "\n",
      "0000011111111111111111111010110101101011110101101101\n",
      "\n",
      "0000000000000000000000000000000000000000000000000000\n",
      "\n"
     ]
    }
   ],
   "source": [
    "AC_cxts=[cxtFromFile(\"AC_Part\"+str(n)+\".cxt\") for n in range(6)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "1b985024",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "eeea6f24",
   "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",
      "111111111111111\n",
      "\n",
      "011111111111111\n",
      "\n",
      "011111111111111\n",
      "\n",
      "011111111111111\n",
      "\n",
      "000011111111111\n",
      "\n",
      "011111111111111\n",
      "\n",
      "011111111111111\n",
      "\n",
      "001110011111111\n",
      "\n",
      "011111111111111\n",
      "\n",
      "011010110111111\n",
      "\n",
      "011111111111111\n",
      "\n",
      "010110111101111\n",
      "\n",
      "011011011101111\n",
      "\n",
      "001111110101111\n",
      "\n",
      "000000000000001\n",
      "\n",
      "B\n",
      "\n",
      "\n",
      "\n",
      "\n",
      "\n",
      "1111111111111111111111111111111111111111111111111111\n",
      "\n",
      "0111111111111111111111111111111111111111111111111111\n",
      "\n",
      "0111111111111111111111111111111111111111111111111111\n",
      "\n",
      "0111111111111111111111111111111111111111111111111111\n",
      "\n",
      "0000111111111111111111111111111111111111111111111111\n",
      "\n",
      "0111111111111111111111111111111111111111111111111111\n",
      "\n",
      "0111111111111111111111111111111111111111111111111111\n",
      "\n",
      "0011100111111111111111111111111111111111111111111111\n",
      "\n",
      "0111111111111111111111111111111111111111111111111111\n",
      "\n",
      "0110101101111111111111111111111111111111111111111111\n",
      "\n",
      "0111111111111111111111111111111111111111111111111111\n",
      "\n",
      "0101101111011111111111111111111111111111111111111111\n",
      "\n",
      "0110110111011111111111111111111111111111111111111111\n",
      "\n",
      "0011111101011111111111111111111111111111111111111111\n",
      "\n",
      "0000000000000011111111111111111111111111111111111111\n",
      "\n",
      "0111111111111111111111111111111111111111111111111111\n",
      "\n",
      "0111111111111111111111111111111111111111111111111111\n",
      "\n",
      "0011111111111110011111111111111111111111111111111111\n",
      "\n",
      "0111111111111111111111111111111111111111111111111111\n",
      "\n",
      "0110111111111110110111111111111111111111111111111111\n",
      "\n",
      "0111111111111111111111111111111111111111111111111111\n",
      "\n",
      "0101111111111110111101111111111111111111111111111111\n",
      "\n",
      "0110111111111111011101111111111111111111111111111111\n",
      "\n",
      "0011111111111111110101111111111111111111111111111111\n",
      "\n",
      "0000011111111110000000001111111111111111111111111111\n",
      "\n",
      "0111111111111111111111111111111111111111111111111111\n",
      "\n",
      "0111111111011110111111111011111111111111111111111111\n",
      "\n",
      "0111111111111111111111111111111111111111111111111111\n",
      "\n",
      "0111111101111110111111111110111111111111111111111111\n",
      "\n",
      "0111111111011111011111111110111111111111111111111111\n",
      "\n",
      "0011111111111111111111111010111111111111111111111111\n",
      "\n",
      "0011111101011010001111111000000111111111111111111111\n",
      "\n",
      "0111111111111111111111111111111111111111111111111111\n",
      "\n",
      "0111110111111110111111111111111101111111111111111111\n",
      "\n",
      "0111111111011111110111111111111101111111111111111111\n",
      "\n",
      "0110111111111111111111111011111101111111111111111111\n",
      "\n",
      "0110110111010110110011111001111100001111111111111111\n",
      "\n",
      "0111111111111111111111111111111111111111111111111111\n",
      "\n",
      "0111101111111110111111111111111111111011111111111111\n",
      "\n",
      "0111110111111111011111111111111111111011111111111111\n",
      "\n",
      "0111111101111111110111111111111111111011111111111111\n",
      "\n",
      "0111111111011111111101111111111111111011111111111111\n",
      "\n",
      "0101111111111111111111111011111111111011111111111111\n",
      "\n",
      "0101101111001110111100111001111111111001100111111111\n",
      "\n",
      "0110111111111111111111111110111111111011111111111111\n",
      "\n",
      "0110101100111110110011111110011111111001011101111111\n",
      "\n",
      "0110110111010111011101011110101111111010101101111111\n",
      "\n",
      "0011111111111111111111111111111101111011111111111111\n",
      "\n",
      "0011100011111110001111111111111100111000111111101111\n",
      "\n",
      "0011111101011011110101101111111101011011001111101111\n",
      "\n",
      "0000011111111111111111111010110101101011110101101111\n",
      "\n",
      "0000000000000000000000000000000000000000000000000001\n",
      "\n"
     ]
    }
   ],
   "source": [
    "MA_cxts=[cxtFromFile(\"MA_Part\"+str(n)+\".cxt\") for n in range(6)]"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "384eb85c",
   "metadata": {},
   "source": [
    "### 2. Generation of maximal antichains for n in {0,1,2,3,4,5} "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "id": "fac86130",
   "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 352 ms, sys: 6.53 ms, total: 358 ms\n",
      "Wall time: 357 ms\n"
     ]
    }
   ],
   "source": [
    "%%time\n",
    "MAs=[CountAllClosures(c) for c in  MA_cxts[:6]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "id": "851571c1",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 1, 2, 3, 32, 14094]"
      ]
     },
     "execution_count": 35,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "MAs"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "96de460b",
   "metadata": {},
   "source": [
    "### 3. Counting of  antichains for n in {0, 1, 2, 3, 4, 5}  (https://oeis.org/A302250)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "id": "c6f3cedc",
   "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",
      "3000000\n",
      "4000000\n",
      "5000000\n",
      "6000000\n",
      "7000000\n",
      "8000000\n",
      "9000000\n",
      "10000000\n",
      "11000000\n",
      "12000000\n",
      "13000000\n",
      "14000000\n",
      "15000000\n",
      "16000000\n",
      "17000000\n",
      "18000000\n",
      "19000000\n",
      "20000000\n",
      "21000000\n",
      "22000000\n",
      "23000000\n",
      "24000000\n",
      "25000000\n",
      "26000000\n",
      "27000000\n",
      "28000000\n",
      "29000000\n",
      "30000000\n",
      "31000000\n",
      "32000000\n",
      "33000000\n",
      "34000000\n",
      "35000000\n",
      "36000000\n",
      "37000000\n",
      "38000000\n",
      "39000000\n",
      "40000000\n",
      "41000000\n",
      "42000000\n",
      "43000000\n",
      "44000000\n",
      "45000000\n",
      "46000000\n",
      "47000000\n",
      "48000000\n",
      "49000000\n",
      "50000000\n",
      "51000000\n",
      "52000000\n",
      "53000000\n",
      "54000000\n",
      "55000000\n",
      "56000000\n",
      "57000000\n",
      "58000000\n",
      "59000000\n",
      "60000000\n",
      "61000000\n",
      "62000000\n",
      "63000000\n",
      "64000000\n",
      "65000000\n",
      "66000000\n",
      "67000000\n",
      "68000000\n",
      "69000000\n",
      "70000000\n",
      "71000000\n",
      "72000000\n",
      "73000000\n",
      "74000000\n",
      "75000000\n",
      "76000000\n",
      "77000000\n",
      "78000000\n",
      "79000000\n",
      "Branch terminated with -1\n",
      "CPU times: user 26min 37s, sys: 2.48 s, total: 26min 39s\n",
      "Wall time: 26min 44s\n"
     ]
    }
   ],
   "source": [
    "%%time\n",
    "ACs=[CountAllClosures(c) for c in  AC_cxts[:6]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "id": "da340786",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[2, 2, 3, 10, 347, 79814832]"
      ]
     },
     "execution_count": 37,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "ACs"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "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.9.7"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}