PowersetGenerationPost.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Generating Power sets: Two Approaches (Part 1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Overview\n",
    "\n",
    "In this three post series, we will demonstrate how to construct the power set of a given source set using two different, but functionally-equivalent, methods. In case you're wondering, the power set of a set $S$ is the collection of all (unique) subsets of $S$, including the empty set and $S$ itself. In order to include subsets as members of the power set, we will define a new object class, `ModSet()`, to encapsulate member sets in \"hashable\" containers.  \n",
    "\n",
    "In part one, we'll use a ~~minimal~~ working example to demonstrate our solution to the subset inclusion problem.  In part two, we construct the `ModSet()` object with all the methods necessary to support power set generation by two distinct approaches. Finally, in part three we develop and run binary mask and recursive routines for generating power sets in Python."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Power sets defined and how to build them\n",
    "\n",
    "Now, a bit about power sets.  \n",
    "\n",
    "If a set $S$ has $n$ elements, its power set will have $2^n$ member subsets; these include the complete \"source\" set, $S$ itself, as well as the empty set, $\\emptyset$. For example, the power set of set $\\{x,y,z\\}$ is: $\\{\\emptyset, \\{x\\}, \\{y\\}, \\{z\\}, \\{x, y\\}, \\{x, z\\},  \\{y, z\\}, \\{x, y, z\\}\\}$. Please notice that there are $2^3=8$ subset elements, all of which are unique; that is, no two subsets contain the same collection of members.\n",
    "\n",
    "Why $2^n$? Because all possible subsets can be formed by selecting their members according to digit occurance in the base-2 integers that count from $0$ to $2^n$ \n",
    "\n",
    "Clear as mud, right? Don't worry, we'll explain."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### The Binary Mask approach\n",
    "\n",
    "Say we have a source set comprised of four members, $\\{a,b,c,d\\}$. The corresponding mask will have four digits that can each take on values of either $0$ or $1$. If a mask digit equals $1$ we keep the element in the corresponding location of the source set, if a digit is $0$, we reject the corresponding element. \n",
    "\n",
    "Here's an illustrative example: binary mask $0101$ operating on source set $\\{a,b,c,d\\}$ would form subset member $\\{b,d\\}$ of the power set.  Similarly, binary mask $1110$ selects subset $\\{a,b,c\\}$. Using the same rule, mask $0000$ selects $\\emptyset$, while $1111$ forms the original source set of all four elements. There are $2^4=16$ unique bit combinations in a 4-digit binary mask, so there are $16$ unique member subsets in the power set of a four-element source set. Now, extending this procedure to a set comprised of $n$ elements rather than $4$, you can see that its power set will have $2^n$ member subsets by the same rule (the binomal theorem).\n",
    "\n",
    "The above procedure may seem to have a certain efficiency and elegance in its directness; one might go so far to say that it is the \"best\" way to generate a power set. In this series, we'll call this method the \"Binary Mask approach\".\n",
    "\n",
    "But there is another method we can use to build power sets..."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### The Recursive approach\n",
    "\n",
    "Alternatively, you can take your source set, $\\{a,b,c,d\\}$, remove one of its members, $a$, then define a new subset with the members that remain, $\\{b,c,d\\}$, and include it as a new element of the power set. Repeating this process, using all elements on all subsets, you will produce the complete power set of the original source set. \n",
    "\n",
    "For example: removing $b$ from our source set leaves subset $\\{a,c,d\\}$. Removing element $c$ from subset $\\{a,c,d\\}$ leaves subset $\\{a,d\\}$.  Taking $a$ from subset $\\{a,d\\}$ results in subset $\\{d\\}$. And finally, removing element $d$ from subset $\\{d\\}$ results in $\\emptyset$. Then we go all the way back up to the top, this time taking $c$ from $\\{a,b,c,d\\}$ and repeat the entire stripping procedure until we are left with $\\emptyset$ as above. Then do the same starting with members $d$ and $a$; repeating the full stripping procedure for each. Notice that we could have removed any element from any set; a recursive algorithm would remove all elements, one-by-one, from each subset.  Many duplicate subsets will be generated in this process, so enforcing member uniqueness will be critical. \n",
    "\n",
    "This second procedure to generate power sets we'll call the \"Recursive approach\".  While the Recursive approach may lack the directness and efficiency of the Binary Mask procedure, we hope that coding it will at least prove to be a worthwhile, \"chops-building\", exercise in recursion.\n",
    "\n",
    "Before we can do either of these, however, we need to investigate the behavior of Python's `set()` class. Specifically, if it suffices for our purposes of containing subsets within an all-encompassing superset, in our case: the power set.\n",
    "\n",
    "\\[Spoiler alert... it doesn't.\\]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## The Python set class\n",
    "\n",
    "The set class in python takes only immutable types (e.g. strings, numeric values, and tuples) as members. Under the hood, a `set()` object retains a *hash* or *pointer* to an immutable object that is a member.  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{('alternative', 'facts'), 20.1, 2017, 'covfefe', 'record-setting'}"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "shinyPrez = set([20.1, 2017, ('alternative', 'facts'), 'record-setting'])\n",
    "shinyPrez.add('covfefe')\n",
    "shinyPrez"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Something to notice: the ordering of elements in the set's output string does *not* match their ordering in its definition. Unlike Python's iterable `list()` class, `set()` objects do not retain member ordering. \n",
    "\n",
    "When you try to insert a mutable type, lists or dictionaries for example, Python will spit back an 'unhashable' type error."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "ename": "TypeError",
     "evalue": "unhashable type: 'list'",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[0;31mTypeError\u001b[0m                                 Traceback (most recent call last)",
      "\u001b[0;32m<ipython-input-3-ae90a0c1ba60>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m\u001b[0m\n\u001b[0;32m----> 1\u001b[0;31m \u001b[0mshinyPrez\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0madd\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0;34m'Cambridge'\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;34m'Analytica'\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m",
      "\u001b[0;31mTypeError\u001b[0m: unhashable type: 'list'"
     ]
    }
   ],
   "source": [
    "shinyPrez.add(['Cambridge', 'Analytica'])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "See, no dice.  Also, because `set()` objects are mutable, the same goes if you attempt to include a `set` as a member of another `set`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{('impeachment', 'procedings')}"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "woopsy = set([('impeachment', 'procedings')])\n",
    "woopsy"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "ename": "TypeError",
     "evalue": "unhashable type: 'set'",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[0;31mTypeError\u001b[0m                                 Traceback (most recent call last)",
      "\u001b[0;32m<ipython-input-5-3116c73d2c5b>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m\u001b[0m\n\u001b[0;32m----> 1\u001b[0;31m \u001b[0mshinyPrez\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0madd\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mwoopsy\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m",
      "\u001b[0;31mTypeError\u001b[0m: unhashable type: 'set'"
     ]
    }
   ],
   "source": [
    "shinyPrez.add(woopsy)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Though you can join sets together, by combining unique members into a single pool, with the `set.union()` operation."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{('alternative', 'facts'),\n",
       " ('impeachment', 'procedings'),\n",
       " 20.1,\n",
       " 2017,\n",
       " 'covfefe',\n",
       " 'record-setting'}"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "shinyPrez = shinyPrez.union(woopsy)\n",
    "shinyPrez"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now, because separate instances of a class are allocated their own locations in memory, they are hashable; even if they contain unhashable values as attributes. And, even if the values of the attributes of the two instances are equivalent."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "<class 'set'>\n",
      "[<class '__main__.Advisor'>, <class '__main__.Advisor'>]\n",
      "[<class 'set'>, <class 'set'>]\n"
     ]
    }
   ],
   "source": [
    "class Advisor():\n",
    "    def __init__(self):\n",
    "        self.val = {'Presidential', 'pardon'}  # Attribute contains unhashable set\n",
    "        \n",
    "RogerS = Advisor()   # has set for attribute .val\n",
    "PaulM = Advisor()  # has same set as above for its attribute .val\n",
    "modelCitz = set([PaulM, RogerS])  # include the two instances as members of a set\n",
    "print(type(modelCitz))           # c is indeed a set\n",
    "print([type(el) for el in modelCitz]) # members of the set are instances of Advisor class\n",
    "print([type(el.val) for el in modelCitz])  # attributes of member instances are sets"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We adopted the above definition from [Max Bernstein's blog](https://bernsteinbear.com/blog/recursive-python-objects/).  Also, we can instruct that instances of the class, when called, define themselves as their `.val` attribute<sup>[1](#Sources-(part-1))</sup>."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{{'pardon', 'Presidential'}}"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "class Advisor():\n",
    "    def __init__(self):\n",
    "        self.val = {'Presidential', 'pardon'}\n",
    "    def __repr__(self):  # method to generate representative code string\n",
    "        return self.val.__repr__()  # return __repr__ code string for the\n",
    "                                    # Advisor().val attribute\n",
    "\n",
    "MichaelF = Advisor()\n",
    "noHarmDone = set([MichaelF])\n",
    "noHarmDone"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A quick look might suggest that we bypassed `set()`'s exclusion of mutables here. But don't be fooled. While we have the *appearence* of having a `set` object contained within another `set` object, what we actually have is a `set` that contains a hash to an instance of `Advisor()` that has a `set` as an attribute."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "<class 'set'>\n",
      "<class '__main__.Advisor'>\n",
      "<class 'set'>\n"
     ]
    }
   ],
   "source": [
    "print(type(noHarmDone))  # Notice that set()'s lack of indexing\n",
    "print(type(list(noHarmDone)[0]))  # methods can be a bit \n",
    "print(type(list(noHarmDone)[0].val))  # of a pain..!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The skeptical Python programmer at this stage is likely asking her/his/them-self: \"why don't you just use a `list` object rather than defining a whole 'nother class for chrissakes!?!\"  Number 1, lists are not hashable; for our power set generatation routines to come, we require a container that is.  Number 2, lists permit duplicate entries; enforcing member uniqueness would require more coding. Number 3, lists preserve element ordering; while not a deal-breaker for our purposes, lists do not mathematically qualify as sets for this reason and others."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In part two, we'll define a new class, `ModSet()`, that will behave much like Python's `set()` class, but with an added `set`-valued attribute. Our `ModSet()` class will employ the same approach just demonstrated above: use of a hashable class instance to contain unhashable set objects. With these container instances themselves eligible for membership in a super-`set()` object. Use of `ModSet` objects will allow us to form an all-encompassing powerset that--indirectly--has sub-`set()` instances as members. More than a cosmetic device, defining a set container class in this way will allow the powerset of a given `set` object to be generated using Binary Mask and Recursion-based algorithms later on in part three.\n",
    "\n",
    "## Sources (part 1)\n",
    "\n",
    "1. Max Bernstein, [Recursive Python Objects](https://bernsteinbear.com/blog/recursive-python-objects/), https://bernsteinbear.com/blog."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Generating Power sets: Two Approaches (Part 2)\n",
    "\n",
    "In part one, we showed that instances classes are hashable, so they can be included as elements of a `set` object. If the class instance happens to have a `set`-valued attribute, we effectively have a `set` with another `set` as a member, made possible by the instance acting as a \"container\"<sup>[1](#Sources-(part-2))</sup>.  In the post that follows, we'll craft a new class that incorporates the container behavior illustrated in part one, as well as a number of other methods that will prove necessary when we build power sets in part three. \n",
    "\n",
    "## Define a set container class\n",
    "\n",
    "Using the illustrative example in part one, we will define a new class, `ModSet()`, with the same constructor and representation methods. New instances of the class will require a set argument, either occupied or empty. In addition, we will define methods to copy, nest and unnest instances of the class."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class ModSet():\n",
    "    \n",
    "    # Instance constructor\n",
    "    def __init__(self, setElement):\n",
    "        self.val = setElement  # set arg saved in .val attribute\n",
    "    \n",
    "    # String eval representation of self instance \n",
    "    def __repr__(self):\n",
    "        return self.val.__repr__() # Return string eval represent.\n",
    "                                   # of string object in .val\n",
    "    \n",
    "    # Method to make a copy of self instance\n",
    "    def __copy__(self):\n",
    "        return ModSet(self.val)\n",
    "    \n",
    "    # Modify .val to contain the set of itself, of itself, ...\n",
    "    # nesting .val \"depth\" number of levels.\n",
    "    def pushDown(self, depth):\n",
    "        while depth > 0:\n",
    "            self.val = set([ModSet(self.val)])\n",
    "            depth -= 1     \n",
    "    \n",
    "    # Remove one nesting level from set in self.val.\n",
    "    # If un-nested, ignore.\n",
    "    def pullUpOneLevel(self):\n",
    "        listSet = list(self.val)\n",
    "        if len(listSet) == 1:\n",
    "            self.val = listSet[0].val\n",
    "        else:\n",
    "            pass\n",
    "    \n",
    "    # Remove height number of nesting levels from set in\n",
    "    # self.val by repeatedly calling above method\n",
    "    def pullUp(self, height):\n",
    "        while height > 0:\n",
    "            self.pullUpOneLevel()\n",
    "            height -= 1\n",
    "                "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Testing these, let's define a set of mixed immutables and nest it 3 levels deep."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{{{{('televised', 'summit'), 2019, '\"bromance\"', 12.6, 'DMZ'}}}}"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "worldlyPrez = ModSet(set([('televised', 'summit'), 'DMZ', 12.6, 2019, '\\\"bromance\\\"']))\n",
    "worldlyPrez.pushDown(3)\n",
    "worldlyPrez"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Raising that result back up three levels should return the set to how it was originally defined."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{('televised', 'summit'), 2019, '\"bromance\"', 12.6, 'DMZ'}"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "worldlyPrez.pullUp(3)\n",
    "worldlyPrez"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "If you instruct to pull up greater than the set is deep, the extra assentions are ignored."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{('televised', 'summit'), 2019, '\"bromance\"', 12.6, 'DMZ'}"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "worldlyPrez.pullUp(2)\n",
    "worldlyPrez"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Enforcing uniqueness\n",
    "\n",
    "Just like Python's set class, we will make sure that each member of ModSet be unique according to the value of its `.val` attribute.  When a ModSet is comprised of immutables, the `set()` class enforces uniqueness for us automatically.  However, if a ModSet contains other ModSets, we require an additional method to enforce uniqueness among them as well."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class ModSet():\n",
    "    .\n",
    "    .\n",
    "    .\n",
    "    def removeDuplicates(self):\n",
    "        uniqueSet = set()  # initialize as empty the unique set to be built\n",
    "        for s in self.val:  # s is a member of the ModSet().val set\n",
    "            inUniqueSet = False  # initialize match detetion flag as false\n",
    "            sTest = s  # default conditional testing value for s\n",
    "            for us in uniqueSet: # us is a member of the uniqueSet set\n",
    "                usTest = us  # default conditional testing value for us\n",
    "                if isinstance(us, ModSet): # if member us is a ModSet\n",
    "                    usTest = us.val        # change testing value to its attribute\n",
    "                if isinstance(s, ModSet):  # if member s is a ModSet\n",
    "                    sTest = s.val          # change testing value to its attribute\n",
    "                if usTest == sTest:  # compare us and s testing values on this run\n",
    "                    inUniqueSet = True  # if match, set existence flag to true\n",
    "            if not inUniqueSet:    # only add member s to uniqueSet if\n",
    "                uniqueSet.add(s)   # match is NOT detected\n",
    "        self.val = uniqueSet    # set .val to the uniqueSet from above"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "After including `removeDuplicates()` in our class definition we'll test it as follows. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{140437984002736, 140437984002792, 140437984002680}\n",
      "{{('televised', 'summit'), 2019, '\"bromance\"', 12.6, 'DMZ'}, {('televised', 'summit'), 2019, '\"bromance\"', 12.6, 'DMZ'}, {('televised', 'summit'), 2019, '\"bromance\"', 12.6, 'DMZ'}}\n"
     ]
    }
   ],
   "source": [
    "prez1 = ModSet(set([('televised', 'summit'), 'DMZ', 12.6, 2019, '\\\"bromance\\\"']))  # inst. 1\n",
    "prez2 = ModSet(set([('televised', 'summit'), 'DMZ', 12.6, 2019, '\\\"bromance\\\"']))  # inst. 2\n",
    "prez3 = ModSet(set([('televised', 'summit'), 'DMZ', 12.6, 2019, '\\\"bromance\\\"']))  # inst. 3\n",
    "print(set([id(prez1), id(prez2), id(prez3)]))  # each instance held in its own memory block\n",
    "\n",
    "modSetOfPrez = ModSet(set([prez1, prez2, prez3]))  # define a ModSet of ModSet instances\n",
    "print(modSetOfPrez.val)  # set class sees each instance as unique though they contain \n",
    "                         # equivalent values in their attributes"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now let's call our uniqueness filter.  Only one member should remain."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{{('televised', 'summit'), 2019, '\"bromance\"', 12.6, 'DMZ'}}\n"
     ]
    }
   ],
   "source": [
    "modSetOfPrez.removeDuplicates()  # enforce uniqueness according to attribute value\n",
    "print(modSetOfPrez)   # result after applying removeDuplicates()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Set operator methods\n",
    "\n",
    "For the power set routines to come, we need instances of `ModSet()` to join by union and also separate by set-subtraction.  Below, we define methods for these operations as well as set-intersection."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class ModSet():\n",
    "    .\n",
    "    .\n",
    "    .\n",
    "    # union-join multiple items, enforce that ModSet members be unique\n",
    "    def union(self, *modSets):\n",
    "        for modSet in modSets:\n",
    "            self.val = self.val.union(modSet.val)  # this is union method from set class\n",
    "            self.removeDuplicates()  # removes duplicate-valued instances of ModSet members\n",
    "    \n",
    "    # take set intersection of multiple items\n",
    "    def intersection(self, *modSets):\n",
    "        for modSet in modSets:\n",
    "            self.val = self.val.intersection(modSet.val) # method from set class\n",
    "    \n",
    "    # take set difference of multiple items. Note: arg order matters here! \n",
    "    def difference(self, *modSets):\n",
    "        for modSet in modSets:\n",
    "            self.val = self.val.difference(modSet.val) # method from set class\n",
    "    \n",
    "    # version of above method that returns a new instance for assignment.\n",
    "    # Note: only two arguments here.\n",
    "    def diffFunc(modSet1, modSet2):\n",
    "        return ModSet(set.difference(modSet1.val, modSet2.val))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Testing ModSet Union\n",
    "\n",
    "With the set operation methods now included in the class, let's test union-joining of non-ModSet objects."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{'Congress', 'abuse', 'insurrection', 'obstruction', 'of', 'incitement', 'power'}\n"
     ]
    }
   ],
   "source": [
    "charges = ModSet(set())\n",
    "charge1 = ModSet(set(['obstruction', 'of', 'Congress']))\n",
    "charge2 = ModSet(set(['abuse', 'of', 'power']))\n",
    "charge3 = ModSet(set(['incitement', 'of', 'insurrection']))\n",
    "\n",
    "charges.union(charge1, charge2, charge3)\n",
    "print(charges)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The three separate ModSets have been merged into a single ModSet, `charges`.  Notice that string member `'of'` appears only once, as it should, though it is present in `charge1`, `charge2`, and `charge3`.  Now, we'll test union operation with ModSet members present as well.\n",
    "\n",
    "First, we'll nest down by one level each of the three charges, so that we can test `ModSet.union()`. This time we're interested in the case when ModSet-of-ModSets are present in the pool of objects to be joined.  By \"ModSet-of-ModSet\",  we mean a ModSet instance that has another ModSet instance as a member of its set-valued `.val` attribute--the result of `ModSet.pushDown(1)`. During the union call, these ModSet-of-ModSet objects will be routed through paths of `.removeDuplicates()` that we've set up specifically for them. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{'Congress', 'abuse', 'insurrection', 'obstruction', 'of', 'incitement', 'all', 'power', {'Congress', 'obstruction', 'of'}, {'insurrection', 'of', 'incitement'}, 'news', 'fake', {'power', 'of', 'abuse'}}\n"
     ]
    }
   ],
   "source": [
    "charge1.pushDown(1)\n",
    "charge2.pushDown(1)\n",
    "charge3.pushDown(1)\n",
    "\n",
    "charges.union(charge1, charge1, charge2, charge3, ModSet(set(['all', 'fake', 'news'])))\n",
    "print(charges)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "You should notice that though we have included `charge1` twice in the method-call, its value, `{'Congress', 'obstruction', 'of'}`, appears just once in the output. So, we may conclude that the `.removeDuplicates()` method does correctly enforce uniqueness among ModSet-of-ModSet members.  Members of `{'all', 'fake', 'news'}` have been included as well. Now that we've shown that `.union()` works as expected, we can move on to test `.intersection()`."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Testing ModSet Intersection"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{{'power', 'of', 'abuse'}, 'the'}"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "claim1 = ModSet(set(['rounding', 'the', 'bend']))  # define a new instance of ModSet\n",
    "claim2 = ModSet(set(['dems', 'stole', 'the', 'election'])) # define another new instance\n",
    "claim1.union(charge1, charge2)  # union-join charges 1 and 2 from above with claim1 \n",
    "claim2.union(charge2, charge3)  # union-join charges 2 and 3 from above with claim2\n",
    "claim1.intersection(claim2)  # perform set-intersection of claims 1 and 2\n",
    "claim1  # output the post-intersection result"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Above we form two \"mixed\" `ModSet()` instances that contain both top-level strings as well as sub-ModSets as members. We can see, after joining the two by set intersection, the result is what we expect: only `'the'` remains from the strings and only `charge2` survives among the ModSets. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Testing ModSet Set-difference\n",
    "\n",
    "Above we included two methods for performing set-subtraction within the `ModSet()` class.  The first, called `.difference()`, is an inline function that modifies the original instance from which it is called. Removing `charge2` from `charges` "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'Congress', 'abuse', 'insurrection', 'obstruction', 'of', 'incitement', 'all', 'power', {'Congress', 'obstruction', 'of'}, {'insurrection', 'of', 'incitement'}, 'news', 'fake'}"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "charges.difference(charge2)\n",
    "charges"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "leaves `charges` with all but the `{'abuse', 'of', 'power'}` member in the result. So, check.  \n",
    "\n",
    "The second method, that we've named `.diffFunc()`, is a functional version of set-subtraction that returns the result as a new instance `ModSet()` leaving its originating instances unchaged. To test `.diffFunc()`, we'll now attempt to remove `charge1` from `charges` (since `charge2` has already been removed in the previous step)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'Congress', 'abuse', 'insurrection', 'obstruction', 'of', 'incitement', 'all', 'power', {'insurrection', 'of', 'incitement'}, 'news', 'fake'}"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "chargesReduced = ModSet.diffFunc(charges, charge1)\n",
    "chargesReduced"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "You can see that the value from `charge1`, `{'obstruction', 'of', 'Congress'}`, is absent from `chargesReduced`, though all others from its parent, `charges`, are present.  \n",
    "\n",
    "Lastly, let's examine `charges` to make sure that this particular instance has *not* been modified since last step."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'Congress', 'abuse', 'insurrection', 'obstruction', 'of', 'incitement', 'all', 'power', {'Congress', 'obstruction', 'of'}, {'insurrection', 'of', 'incitement'}, 'news', 'fake'}"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "charges"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "And there the charge remains, in all its glory, one could say...  \n",
    "\n",
    "Though our testing of `ModSet()` above has been far from exhaustive, we hope you are convinced that instances of it will behave as we intend them to. At this point, we can *finally* move on to our main objective: building powersets.  We'll do this in part three to come. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Sources (part 2)\n",
    "\n",
    "1. Max Bernstein, [Recursive Python Objects](https://bernsteinbear.com/blog/recursive-python-objects/), https://bernsteinbear.com/blog."
   ]
  },
  {
   "cell_type": "raw",
   "metadata": {},
   "source": [
    "<a rel=\"license\" href=\"http://creativecommons.org/licenses/by/4.0/\"><img alt=\"Creative Commons License\" style=\"border-width:0\" src=\"https://i.creativecommons.org/l/by/4.0/88x31.png\" /></a><br /><span xmlns:dct=\"http://purl.org/dc/terms/\" property=\"dct:title\">The ModSet() class</span> by <a xmlns:cc=\"http://creativecommons.org/ns#\" href=\"nullexit.org\" property=\"cc:attributionName\" rel=\"cc:attributionURL\">nullexit.org</a> is licensed under a <a rel=\"license\" href=\"http://creativecommons.org/licenses/by/4.0/\">Creative Commons Attribution 4.0 International License</a>."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Generating Power sets: Two Approaches (Part 3)\n",
    "\n",
    "Last time, in part two, we built and tested our set container class, `ModSet()`, with a variety of methods that will prove useful when we construct the power set.  Methods included copying, nesting/unnesting, filtering to keep only unique members as well as set-union and set-subtraction operations. You will see that most of these will be used, either implicitly or explicity, in both Binary Mask and Recursive methods of generating power sets."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Preliminaries\n",
    "\n",
    "When we are ready to build our power set, we'll measure the time it takes each of the two routines to complete, so we can compare their performance. As a preliminary, let's import the `time` module so it stands at ready."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [],
   "source": [
    "import time"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Of course we will need an example source set to operate on. Let's define it now and be done with it."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 65,
   "metadata": {},
   "outputs": [],
   "source": [
    "clumsyPrez = ModSet(set([ 6.1, 2021, \"fight like hell\", \"we love you\", ('impeachment', '#2')]))\n",
    "#clumsyPrez = ModSet(set(['a', 'b', 'c', 'd', 'e']))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Binary Mask Power set Generator\n",
    "\n",
    "In this iterative-based approach, we will populate the power set by applying binary masks to extract out member subsets, one-by-one, from the source set in `ModSet().val`. If you recall, a verbal description of power set generation using a binary mask we discussed way back in part one; you can find it [here](#The-Binary-Mask-approach). Below, we first provide an overview of our binary mask power set generator routine, followed by the routine itself, with heavy commenting, concluded with a detailed walk-through after that.\n",
    "\n",
    "The method, named `.powerSet_bin()`, contains 19 lines and calls `.pushDown()` and `.union()` sibling methods.  Though we could use NumPy here to make mask generation and member extraction more compact, we did not want to confound the comparision (to the recursive approach to follow) by incorporating functionality of an external module.  Already, the code has been somewhat compressed by use of generator expressions.\n",
    "\n",
    "The routine below can be divided into two main blocks: variable initialization, and the run-time loop that builds each binary mask for extracting the corresponding subset on each iteration. The loop populates the powerset member-by-member and terminates when all $2^n$ members have been added. Because indexing is crucial in this approach, you'll notice heavy use of `range()` and `list()` datatypes.  As you'll see later, the recursive approach requires no such crutch."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class ModSet():\n",
    "    .\n",
    "    .\n",
    "    .\n",
    "    # Generate powerset via direct, binary mask approach\n",
    "    def powerSet_bin(self):\n",
    "        \n",
    "        ## Initialize local variables ##\n",
    "        S = list(self.val)         # convert to list for indexing\n",
    "        setSize = len(self.val)    # count number of members in source set\n",
    "        psetSize = pow(2, setSize) # calculate the number of elements in the power set\n",
    "        lastIndex = setSize - 1    # index value of last member\n",
    "        setIndices = range(0, setSize)  # make indices list for source set\n",
    "        psetIndices = range(0, psetSize) # make indices list for power set to be built\n",
    "        bMasks = [[False for s in setIndices] for p in psetIndices] # Initialize binary mask       \n",
    "        pSet = ModSet(set())  # initialize power set as empty ModSet() instance\n",
    "        pSet.pushDown(1)  # and nest it down one level for later joining\n",
    "        \n",
    "        ## Populate powerset with each subset, one at a time ##\n",
    "        for i in psetIndices: # loop through each member of power set\n",
    "            \n",
    "            ## Generate binary mask for subset i of power set ##\n",
    "            diff = i  # assign current pSet index as initial bit-flip threshold\n",
    "            for j in setIndices: # loop through each digit of mask\n",
    "                \n",
    "                if (diff >= pow(2, lastIndex - j)): # if threshold >= highest digit, then\n",
    "                    bMasks[i][lastIndex - j] = True  # set corresp. mask digit to \"true\"\n",
    "                    diff -= pow(2, lastIndex - j)   # reduce threshold for next mask digit\n",
    "                    \n",
    "            ## Form subset i of power set ##\n",
    "            # Use generator expression for compactness\n",
    "            dummySet = ModSet(set([S[k] for k in setIndices if bMasks[i][k] == True]))\n",
    "            dummySet.pushDown(1)  # nest ModSet instance down one level for union join\n",
    "            pSet.union(dummySet)  # include new subset in power set\n",
    "            \n",
    "        return pSet, bMasks  # return complete power set and binary masks as output"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "With the binary mask routine complete, we're ready to build our power set.  Below we've sandwiched the call within two `time.time()` reads, so we can measure its runtime duration. Let's examine `bMasks` output first."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 66,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[[False, False, False, False, False],\n",
       " [True, False, False, False, False],\n",
       " [False, True, False, False, False],\n",
       " [True, True, False, False, False],\n",
       " [False, False, True, False, False],\n",
       " [True, False, True, False, False],\n",
       " [False, True, True, False, False],\n",
       " [True, True, True, False, False],\n",
       " [False, False, False, True, False],\n",
       " [True, False, False, True, False],\n",
       " [False, True, False, True, False],\n",
       " [True, True, False, True, False],\n",
       " [False, False, True, True, False],\n",
       " [True, False, True, True, False],\n",
       " [False, True, True, True, False],\n",
       " [True, True, True, True, False],\n",
       " [False, False, False, False, True],\n",
       " [True, False, False, False, True],\n",
       " [False, True, False, False, True],\n",
       " [True, True, False, False, True],\n",
       " [False, False, True, False, True],\n",
       " [True, False, True, False, True],\n",
       " [False, True, True, False, True],\n",
       " [True, True, True, False, True],\n",
       " [False, False, False, True, True],\n",
       " [True, False, False, True, True],\n",
       " [False, True, False, True, True],\n",
       " [True, True, False, True, True],\n",
       " [False, False, True, True, True],\n",
       " [True, False, True, True, True],\n",
       " [False, True, True, True, True],\n",
       " [True, True, True, True, True]]"
      ]
     },
     "execution_count": 66,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "tStart = time.time() # clock start timestamp\n",
    "pSet_bin, bMasks = clumsyPrez.powerSet_bin() # call our binary mask power set generator\n",
    "duration = time.time() - tStart # calc run duration by subtracting tStart from current time.\n",
    "bMasks # show list of binary masks"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Above, you can notice that masks progress from all `false` to all `true` in a logical pattern. This ordering would be a great feature if we cared about how members are ordered in our power set. But sets, strictly defined, are not distinguished by the ordering of their members<sup>[2](#Sources)</sup>.  That is, set $\\{a, b, c\\}$ is equivalent to set $\\{c, a, b\\}$ and $\\{b, a, c\\}$, and so on and so forth.\n",
    "\n",
    "So, after taking a look at our power set in `pSet_bin`, we see that the nice ordering was all for naught."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 83,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The Binary Mask approach took 0.007008 seconds to complete.\n",
      "The power set contains 32 subset elements\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "{set(),\n",
       " {'fight like hell', ('impeachment', '#2'), 2021, 6.1},\n",
       " {'fight like hell', ('impeachment', '#2'), 2021},\n",
       " {'fight like hell', 2021, 6.1},\n",
       " {'fight like hell', 2021},\n",
       " {'fight like hell', 6.1},\n",
       " {'fight like hell'},\n",
       " {'we love you', 'fight like hell', 6.1},\n",
       " {'we love you', 'fight like hell'},\n",
       " {'we love you', ('impeachment', '#2'), 'fight like hell', 6.1},\n",
       " {'we love you', ('impeachment', '#2'), 'fight like hell'},\n",
       " {'we love you', ('impeachment', '#2'), 2021, 'fight like hell'},\n",
       " {'we love you', ('impeachment', '#2'), 2021, 6.1},\n",
       " {'we love you', ('impeachment', '#2'), 2021},\n",
       " {'we love you', ('impeachment', '#2'), 6.1},\n",
       " {'we love you', ('impeachment', '#2')},\n",
       " {'we love you', 2021, 'fight like hell'},\n",
       " {'we love you', 2021, 6.1, 'fight like hell'},\n",
       " {'we love you', 2021, 6.1},\n",
       " {'we love you', 2021},\n",
       " {'we love you', 6.1},\n",
       " {'we love you'},\n",
       " {('impeachment', '#2'), 'fight like hell', 6.1},\n",
       " {('impeachment', '#2'), 'fight like hell'},\n",
       " {('impeachment', '#2'), 2021, 6.1},\n",
       " {('impeachment', '#2'), 2021},\n",
       " {('impeachment', '#2'), 6.1},\n",
       " {('impeachment', '#2')},\n",
       " {2021, 6.1, 'we love you', ('impeachment', '#2'), 'fight like hell'},\n",
       " {2021, 6.1},\n",
       " {2021},\n",
       " {6.1}}"
      ]
     },
     "execution_count": 83,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Report duration of binary mask power set generation\n",
    "print('The Binary Mask approach took %0.6f seconds to complete.'%(duration))\n",
    "print('The power set contains %i subset elements'%(len(pSet_bin.val)))\n",
    "pSet_bin.val # show power set output; remember, this is a set!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "From the power set output string above, it looks like we have many sub-`set` instances as members of one big super-`set`.  But, if you recall from all the way back in part one, this is *not* the case; our power set `pSet_bin` is actually a `ModSet()` object, whose `.val` attribute is a `set`, each element of which is another `ModSet()` instance that contains one unique sub-`set` of the original source set (as its `.val` attribute). We defined the `ModSet.__repr__()` method to return the code representation of its `.val` attribute; that's the reason why the return string from calling `pSet_bin.val` appears in this set-resembling format. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Recursive Power set generator\n",
    "\n",
    "In part one, we went over the recursive algorithm that we used to design our recursive power set generator below. You can find it [here](#The-Recursive-approach) if you would like a refresher.\n",
    "\n",
    "Our recursion-based method for generating powersets contains just 11 lines of code but calls four sibling methods, as well as itself, to run. Though `.powerSet_rec()` has fewer lines than `.powerSet_bin()`, it relies more heavily upon behavior of sibling methods in the `ModSet()` class, i.e. `.__copy__()`, `.pushDown()`, `.diffFunc()` and `.union()` to perform the respective obligatory processing tasks of duplication, nesting, extraction, joining and filtering. Unlike the Binary Mask approach above, indexing is not needed here, and hence, not employed. Through recursion, we can generate the identical power set using thoughtfully-placed set-subtraction, -union and -filtering operations.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class ModSet():\n",
    "    .\n",
    "    .\n",
    "    .\n",
    "    # Generate power set recursively.\n",
    "    def powerSet_rec(self):\n",
    "        \n",
    "        pSet = self.__copy__()      # Preserve self instance; its copy, pSet\n",
    "                                    # will be altered\n",
    "        pSet.pushDown(1)            # Nest pSet for later joining.\n",
    "              \n",
    "        if len(self.val) > 0:       # Recursion termination condition\n",
    "            for elSet in self.val:  # Iterate through members of set self.val\n",
    "                # Generate subset that remains after removing current\n",
    "                # element, elSet, from set self.val\n",
    "                dummySet = self.diffFunc(ModSet(set([elSet]))) \n",
    "                # To current powerset, append the powerset of the\n",
    "                # subset from previous step\n",
    "                pSet.union(dummySet.powerSet_rec())  # Self-call power set method,\n",
    "                                                     # union join power set of \n",
    "                                                     # dummySet with pSet\n",
    "            return pSet             # Return power set at current \n",
    "                                    # level of recursion\n",
    "        else:\n",
    "            dummySet = ModSet(set())  # Generate instance of ModSet of empty set\n",
    "            dummySet.pushDown(1)      # Nest empty set down one level so it can\n",
    "            return dummySet           # be union-joined in the recursion level\n",
    "                                      # above (that called this current run)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To summarize the program flow: first a duplicate of the calling instance is made to serve as the (local) power set within our routine. This instance is promptly pushed down one level so it can be joined by union later, if necessary. Next, the number of elements in the calling instance are counted.  If empty, an empty `ModSet()` instance is returned on exit of the routine. This case path is the exit condition for the recursive flow; eventually all calling instances will dwindle down to empty as members are stripped from them in the alternative, non-empty, case that we'll describe next.  \n",
    "\n",
    "If the calling instance is not empty, `.powerSet_rec()` iterates over the elements therein, each time subtracting out the current element, `elSet`, and calling itself again to build the power set from elements that remain. Output from this recursive call is then joined by union with `pSet`.  Remember that every time `pSet.union()` runs, it calls the filtering method `removeDuplicates()` to retain only unique members in `pSet` as it is assembled.  \n",
    "\n",
    "When the loop completes, and all subsets have been included at the present level, the local instance of `pSet` is returned so that it can be union-joined with the `pSet` instance inside the calling-function one level above. The method continues in this fashion until `pSet` at the top-most level of recursion is fully populated, at which point output is returned in response to the initial method call.\n",
    "\n",
    "\\[Phew..!\\]\n",
    "\n",
    "Let's give it a whirl and gauge its efficiency."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 84,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The Recursive approach took 0.006541 seconds to complete.\n",
      "The power set contains 32 subset elements\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "{set(),\n",
       " {'fight like hell', ('impeachment', '#2'), 2021, 6.1},\n",
       " {'fight like hell', ('impeachment', '#2'), 2021},\n",
       " {'fight like hell', 2021, 6.1},\n",
       " {'fight like hell', 2021},\n",
       " {'fight like hell', 6.1},\n",
       " {'fight like hell'},\n",
       " {'we love you', 'fight like hell', 6.1},\n",
       " {'we love you', 'fight like hell'},\n",
       " {'we love you', ('impeachment', '#2'), 'fight like hell', 6.1},\n",
       " {'we love you', ('impeachment', '#2'), 'fight like hell'},\n",
       " {'we love you', ('impeachment', '#2'), 2021, 'fight like hell'},\n",
       " {'we love you', ('impeachment', '#2'), 2021, 6.1},\n",
       " {'we love you', ('impeachment', '#2'), 2021},\n",
       " {'we love you', ('impeachment', '#2'), 6.1},\n",
       " {'we love you', ('impeachment', '#2')},\n",
       " {'we love you', 2021, 'fight like hell'},\n",
       " {'we love you', 2021, 6.1, 'fight like hell'},\n",
       " {'we love you', 2021, 6.1},\n",
       " {'we love you', 2021},\n",
       " {'we love you', 6.1},\n",
       " {'we love you'},\n",
       " {('impeachment', '#2'), 'fight like hell', 6.1},\n",
       " {('impeachment', '#2'), 'fight like hell'},\n",
       " {('impeachment', '#2'), 2021, 6.1},\n",
       " {('impeachment', '#2'), 2021},\n",
       " {('impeachment', '#2'), 6.1},\n",
       " {('impeachment', '#2')},\n",
       " {2021, 6.1, 'we love you', ('impeachment', '#2'), 'fight like hell'},\n",
       " {2021, 6.1},\n",
       " {2021},\n",
       " {6.1}}"
      ]
     },
     "execution_count": 84,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "tStart = time.time()\n",
    "pSet_rec = clumsyPrez.powerSet_rec()\n",
    "duration = time.time() - tStart\n",
    "print('The Recursive approach took %0.6f seconds to complete.'%(duration))\n",
    "print('The power set contains %i subset elements'%(len(pSet_rec.val)))\n",
    "pSet_rec.val\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "As promised, we see the same power set as we saw from the Binary Mask approach. But unlike that approach, there is no mask output for us to examine this time."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Quick-and-dirty efficiency comparison\n",
    "\n",
    "For a given programming objective, recursive algorithms tend to be less efficient than their iterative equivalents when used in imperative-based languages, like Python, where iteration is preferred<sup>[3](#Sources)</sup>.  Below we hobbled together a quick script to measure, and statistically compare, processing times of the two methods of power set generation of `clumsyPrez`. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 91,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<matplotlib.legend.Legend at 0x7fba1b76b860>"
      ]
     },
     "execution_count": 91,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAYUAAAEWCAYAAACJ0YulAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4xLjMsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy+AADFEAAAgAElEQVR4nO3de5gU1ZnH8e/rgAwid9DIRQEF10FAFFE0blASRUBQg8FEURPQeFmja1yRmKwYdaPRjVmjMXE1IGoEAhFMNAmGBDUaJYyiIpcFEcMIAqLcBJTLu3+c00Uz9Aw9w/T00Pw+zzPP1OXUqXOqquvtOlV9ytwdERERgAPyXQAREak7FBRERCShoCAiIgkFBRERSSgoiIhIQkFBREQSCgqAmf3CzH5QQ3kdbmYbzawojs80s5E1kXcVynC0mb1hZhvM7DtVWK6vmZXlsmwidYGZnWZmC2tpXReZ2fTaWFdNKPigYGZLzWxzPEGuNbNXzOxKM0vq7u5XuvvtWeb15crSuPs/3f1gd99eE+WvppuAme7e2N3vz2M59pqZuZl9GgPtB2b2k1TAlaozs3Fmdke+y7E3qvPlJR5HR6XG3f0ldz86B2XrENdVL21dT7r7mTW9rlwp+KAQnePujYEjgLuAUcCjNb2S9AMhz44A3sl3IWpQD3c/GOgHfAO4vHyCOrTta1wh103qIHcv6D9gKfDlctN6AzuAY+P4OOCOONwK+D2wFvgYeIkQPB+Py2wGNhK+jXcAHBgB/BN4MW1avZjfTOBHwCxgHTANaBHnFQNPAGvi+v4BHJplvQYTTvxr4zqOidP/AmwHtsRydsmwbAtgLLAc+ASYGqf3BcrS0jlwVNp4+nbqC5TF7bAKWAGcCwwA/i9uu++V2+azgfXASuAncfqzwLXlyvcWcG4FZfgN8EDavh0V038G1APaAFOA1cB7wHfSll0bt8lG4NOYd4cM2+cy4GXgZ3GfLQD6pc1vAzwT67gYuDxtf24GWsXx7wPbgCZx/A7gp3G4AXBvPG5WAr8AGpbbtqOAD4HHM5TxKOCFWL6PgIlp8/4FeD6WbyHwtTj9CmAr8HncBr+r4Njqmrb8ytR+jGX+KeG4WR6HG1TzeBgDTAYmAhuA1wnBv9JjD2gUt/GOtH3ZhnB8/T3u4xXAA8CBcdkXY36fxvTD2P1YP4bwOVpL+FwNLrfuBwnH6gbgNeDICrbdP+O6UmXrQzie/laublcDi2J+twNHxvKvByalyh7TDwLmxLK9AnRPmzcK+CDms5C047Ta58zaOjnn648MQSFt512VfsDF4R8RPqD1499pgGXKi50BYHw8WBuSOSh8ABwb00wBnojzvg38DjgIKAJOIJ5A9lCnLvEA/0os402Ek9OBaescWcnyzxI+jM3j8l9K/2Dv6YOZlnYb8J8xj8sJJ+JfA40JJ5YtQKeY/u/A8Dh8MHByHP4a8FraOnoQguSB5csAlBBOkiPS9sccoH3c9gcApbFMBwKdgCXAWRm2wX8RThb1M8y7LNbt32PdhhFOvqlg/gLwc0IQOC7Wu1+c9yLw1Tg8HXgXODtt3nlx+KeEwNIibq/fAT8qt23vJpyIG2Yo41PALbHOxcAX4/RGwDLgm4QgeTwhaHQtvw8rODYaE06q3435NgZOivN+CLwKHAK0Jpygbq/m8TCGEKCGxvQ3EoJ4/SyPvbJy5T4BODnWuQMwH7i+kmM5ySOufzHwPcJxcwbhJHt02ro/JgSeesCTwIQKtl8H0j7/acdT+aDwDNAkbpfPgBmE47UpMA+4NKY9nhBkTyKcIy4lHPcNgKPjvm6Ttu6MwapK58yaOPHW5T8qDgqvArdkOOB+SPg2f9Se8ko7ADpVdFAQTtB3pc0vIXxTKwK+RbnIn2WdfgBMShs/gBB4+qatM2NQAA4jfMtqnmHeLh+2DB+k9O3Ul/CNrSiON47pT0pLX8rOb/wvArcRv0WnpWkQP3Cd4/i9wM/LlWE94YrmXcK3xQPS9se30tKeBPyzXP6jgbHlpg2Ly7auYBtdRvgmbGnTZgHDCQFoO9A4bd6PgHFx+HbgfsLJ40PgOkKTZXIVARghqB+Zlkcf4L20bfs5UFzJMTAeeBhol6FuL5Wb9kvg1vL7sIJ8vw68UcG8d4EBaeNnAUureTyMAV4tdwyvAE7L8tgrq6gOMc31wNOVHMtJHoQvfh+mjqs47SlgTNq6H0mbNwBYUMF6O5BdUDi13HYZlTb+3+y8onyIGHjT5i8EvkS4WlwFfJkMX26q+7e/3FPIpC3hZFTePYRvDdPNbImZ3ZxFXsuqMP99wjeTVoQmqT8BE8xsuZn92MzqZ7G+NjEfANx9R1xH2yyWbQ987O6fZJF2T9b4zhvqm+P/lWnzNxOuCiA0sXUBFpjZP8xsEIC7f0a4XL443vz/OmG7pDve3Zu7+5Hu/v1Y35T0bXsE0CY+ULDWzNYSvv0dmkpgZj0JTQvnufvqSur2gcdPYPQ+Ybu3IWy/DeXmpbb9C4QTzvHA24RmmC8RvsUudvePCN+yDwJK08r5xzg9ZbW7b6mkfDcRgsssM3vHzL6Vtg1OKrcNLgK+UEle6doTTv6Z7HLcsXObpFTleIC0fRf3aVm5/LJmZl3M7Pdm9qGZrSdcCbbKcvE2wLJyx1X6PoUQNFI2sWs9qqP8dqloOx0BfLfc/mxPuDpYTAh+Y4BVZjbBzKq1/dLtl0HBzE4k7PC/lZ/n7hvc/bvu3gk4B7jBzPqlZleQZUXTU9qnDR9OuGz+yN23uvtt7l4CnEJoO7wkiyosJxwsqfpYXMcHWSy7DGhhZs2ySLuJcPJKyfbEsht3X+TuXyc0PdwNTDazRnH2Y4QTVz9gk7v/vSpZpw0vI3zbbpb219jdBwCYWWvgaeDf3P2NPeTbNm7XlMPZ2Zbewswal5uX2vavEC7rzwNecPd5cf5AQsCA0JyzmdCkkypnUw830zPVa/dKu3/o7pe7extCM+TP49M1y+J607fBwe5+VTb5xuWPrGDeLscdO7dJdSWfi/iFoF1afpUde5nq8BDh3k9nd29C+DJgGdJlshxon/5EIrvu06rY0/atqmXAneX250Hu/hSAu//a3b9I2C9O+Gztlf0qKJhZk/gNdQKhXf/tDGkGmdlR8YSwntBUkPr2s5LQ7ldVF5tZiZkdRGiemuzu283sdDPrFh+xXE8IFtk8yjoJGGhm/eKVxXcJ7ZKv7GlBd18B/IFwEmluZvXN7F8rSD4H+IaZFZlZf8I33moxs4vNrHX8NrY2Tt4ey/R3QpPWf7P7VUJVzALWm9koM2sYy32smZ0Yn+CZAjzp7hOzyOsQ4Dtx+1xAuBH5nLsvI2znH5lZsZl1J1wFPRnrsonQHHANO4PAK4QT9wsxzQ7gf4H7zOwQADNra2ZnZVtRM7vAzNrF0U8IJ4TthIckupjZ8Fj2+rH+x8S0ezqGfw98wcyuN7MGZtbYzE6K854Cvm9mrc2sFeH+wRPZljmDE8zs/Lhvriccw6/GeZUdeyuBlmbWNG1aY8JnaKOZ/QtwFbuqrN6vEZrzborbqy/hC+GEatRpNeFYrs55IpP/Ba40s5MsaGRmA+N+OdrMzjCzBoT7NZvJ7vxRqf0lKPzOzDYQou4twE8IN+Iy6Qz8mfDkwN8J7dsz47wfET4Ua83sxiqs/3FCu+SHhLbl1A/KvkB4AmM94cbYC8QPmYUf1P0iU2buvhC4mPB0zEeEA/gcd/88y/IMJwSgBYQ2yesrSHddzDvVBDE1y/wz6Q+8Y2Ybgf8BLizXPDIe6MZenGRi08U5hJu/7xG2zSOEm3ftCG3H11v4zUPq7/AKsnuNcCx8BNwJDHX3NXHe1wltx8sJVx63uvvzacu+QGginJU23phwXyVlFKGZ8tXY3PFnwhVGtk4EXovb8xngOnd/LzZrnQlcGMv3ITtvWEN4FLskHsO77c+4/FcI2/FDwhMyp8fZdxCeIHuL0DT2epxWXdMI90A+IRyT57v71jivwmPP3RcQAtSSWI82hBvV3yDcIP5fwoMU6cYAj8X0XytX588JT/OdTdjfPwcuieupkvil4E7g5biuk6uaR7n8ZhNu2j9A2E6LCfcoIOzTu2KZPyR8kfne3qwPdj5VI5JXZnYJcEW8FM53WS4j3KjPe1kKlZmNIdz4vTjfZZFd7S9XClKHxWa1qwlP04hIHikoSF7FdvTVhDbfX+e5OCL7PTUfiYhIQlcKIiKS2Kc72mrVqpV36NAh38UQEdmnlJaWfuTurTPN26eDQocOHZg9e3a+iyEisk8xs/crmqfmIxERSSgoiIhIQkFBREQS+/Q9BREpLFu3bqWsrIwtWyrrIFayVVxcTLt27ahfP5vOlwMFBRGpM8rKymjcuDEdOnRg105qparcnTVr1lBWVkbHjh2zXk7NRyJSZ2zZsoWWLVsqINQAM6Nly5ZVvupSUBCROkUBoeZUZ1sqKIiISEL3FESkzupw87M1mt/SuwbuMU1RURHdunXD3SkqKuKBBx7glFNOYfny5XznO99h8uTJ1Vr3mDFjuO2221i0aBFHHXUUAPfddx833HAD//jHP+jVq1eV8rvssssYNGgQQ4cOrVZ5KrLfBoXqHGzZHFAism9r2LAhc+bMAeBPf/oTo0eP5oUXXqBNmzbVDggp3bp1Y8KECXz/+98HYPLkyZSUlOx1mWuSmo9ERCqwfv16mjdvDsDSpUs59thjARg3bhznn38+/fv3p3Pnztx0001Z5Xfuuecybdo0AJYsWULTpk1p3XpnF0RXXXUVvXr1omvXrtx6663J9JtvvpmSkhK6d+/OjTfu/tLHH/zgB1x22WXs2LGj2nVN2W+vFEREMtm8eTPHHXccW7ZsYcWKFfzlL3/JmG7OnDm88cYbNGjQgKOPPpprr72W9u3bV5p3kyZNaN++PXPnzmXatGkMGzaMsWPHJvPvvPNOWrRowfbt2+nXrx9vvfUW7dq14+mnn2bBggWYGWvXrt0lz5tuuol169YxduzYGrlJrysFEZE0qeajBQsW8Mc//pFLLrmETO+d6devH02bNqW4uJiSkhLef7/CPuZ2ceGFFzJhwgSmTp3Keeedt8u8SZMmcfzxx9OzZ0/eeecd5s2bR5MmTSguLmbkyJH89re/5aCDDkrS33777axdu5Zf/vKXNfbUloKCiEgF+vTpw0cffcTq1at3m9egQYNkuKioiG3btmWV5znnnMPjjz/O4YcfTpMmTZLp7733Hvfeey8zZszgrbfeYuDAgWzZsoV69eoxa9YsvvrVrzJ16lT69++fLHPiiSdSWlrKxx9/vBe13JWaj0REKrBgwQK2b99Oy5Yt2bRpU43k2bBhQ+6++266dOmyy/T169fTqFEjmjZtysqVK/nDH/5A37592bhxI5s2bWLAgAGcfPLJyZNLAP379+ess85i4MCBTJ8+ncaNG+91+RQURKTOyscTf6l7ChC6injssccoKirKevmRI0dy5ZVXVvqI6YUXXrjbtB49etCzZ0+6du1Kp06dOPXUUwHYsGEDQ4YMYcuWLbg799133y7LXXDBBWzYsIHBgwfz3HPP0bBhw6zLmsk+/Y7mXr16eXVfsqNHUkXqnvnz53PMMcfkuxgFJdM2NbNSd88YtXRPQUREEgoKIiKSUFAQEZGEgoKIiCQUFEREJKGgICIiCf1OQUTqrjFNazi/dXtMkuo6e9u2bXTs2JHHH3+cZs2a1Ww5sjBy5EhuuOGGWu9FVVcKIiJpUn0fzZ07lxYtWvDggw/mbF3bt2+vcN4jjzySl261FRRERCrQp08fPvjgg2T8nnvu4cQTT6R79+67dG09fvx4unfvTo8ePRg+fDgQXoKT/v6Fgw8+GICZM2dy+umn841vfINu3brx6aefMnDgQHr06MGxxx7LxIkTAejbty+zZ8/moYce2qVr7nHjxnHttdcC8MQTT9C7d2+OO+44vv3tb1caZLKl5iMRkQy2b9/OjBkzGDFiBADTp09n0aJFzJo1C3dn8ODBvPjii7Rs2ZI777yTl19+mVatWmXVOd2sWbOYO3cuHTt2ZMqUKbRp04Znnw29LKxbt2sT19ChQ+nTpw8//vGPAZg4cSK33HIL8+fPZ+LEibz88svUr1+fq6++mieffJJLLrlkr+qtoCAikibV99HSpUs54YQT+MpXvgKEoDB9+nR69uwJwMaNG1m0aBFvvvkmQ4cOpVWrVgC0aNFij+vo3bs3HTt2BMLb2G688UZGjRrFoEGDOO2003ZJ27p1azp16sSrr75K586dWbhwIaeeeioPPvggpaWlnHjiiUm5DznkkL2uv5qPRETSpO4pvP/++3z++efJPQV3Z/To0cyZM4c5c+awePFiRowYgbtnfJdBvXr1kjehuTuff/55Mq9Ro0bJcJcuXSgtLaVbt26MHj2aH/7wh7vlNWzYMCZNmsSUKVM477zzMDPcnUsvvTQpz8KFCxkzZsxe119BQUQkg6ZNm3L//fdz7733snXrVs466yx+9atfsXHjRgA++OADVq1aRb9+/Zg0aRJr1qwBSJqPOnToQGlpKQDTpk1j69atGdezfPlyDjroIC6++GJuvPFGXn/99d3SnH/++UydOpWnnnqKYcOGAeElP5MnT2bVqlXJerN90U9l1HwkInVXFo+Q5lLPnj3p0aMHEyZMYPjw4cyfP58+ffoA4cbxE088QdeuXbnlllv40pe+RFFRET179mTcuHFcfvnlDBkyhN69e9OvX79drg7Svf322/zHf/wHBxxwAPXr1+ehhx7aLU3z5s0pKSlh3rx59O7dG4CSkhLuuOMOzjzzTHbs2EH9+vV58MEHOeKII/aqzjnvOtvMioDZwAfuPsjMOgITgBbA68Bwd//czBoA44ETgDXAMHdfWlne6jpbpLCo6+yaVxe7zr4OmJ82fjdwn7t3Bj4BRsTpI4BP3P0o4L6YTkREalFOg4KZtQMGAo/EcQPOAFIP7z4GnBuHh8Rx4vx+VlNvohYRkazk+krhp8BNwI443hJY6+6pN1yXAW3jcFtgGUCcvy6mF5H9yL78Nsi6pjrbMmdBwcwGAavcvTR9coaknsW89HyvMLPZZjZ79erVNVBSEakriouLWbNmjQJDDXB31qxZQ3FxcZWWy+XTR6cCg81sAFAMNCFcOTQzs3rxaqAdsDymLwPaA2VmVg9oCuz200B3fxh4GMKN5hyWX0RqWbt27SgrK0Nf+GpGcXEx7dq1q9IyOQsK7j4aGA1gZn2BG939IjP7DTCU8ATSpcC0uMgzcfzvcf5fXF8XRPYr9evXT37pK/mRjx+vjQJuMLPFhHsGj8bpjwIt4/QbgJvzUDYRkf1arfx4zd1nAjPj8BKgd4Y0W4ALaqM8IiKSmbq5EBGRhIKCiIgkFBRERCShoCAiIgkFBRERSSgoiIhIQkFBREQSCgoiIpJQUBARkYSCgoiIJBQUREQkoaAgIiIJBQUREUkoKIiISEJBQUREEgoKIiKSUFAQEZGEgoKIiCQUFEREJKGgICIiCQUFERFJKCiIiEhCQUFERBIKCiIiklBQEBGRhIKCiIgk6uW7ACJ11pimVUy/LjflEKlFulIQEZGEgoKIiCQUFEREJKGgICIiCQUFERFJKCiIiEhCQUFERBIKCiIiklBQEBGRhIKCiIgkchYUzKzYzGaZ2Ztm9o6Z3RandzSz18xskZlNNLMD4/QGcXxxnN8hV2UTEZHMcnml8Blwhrv3AI4D+pvZycDdwH3u3hn4BBgR048APnH3o4D7YjoREalFOQsKHmyMo/XjnwNnAJPj9MeAc+PwkDhOnN/PzCxX5RMRkd3l9J6CmRWZ2RxgFfA88C6w1t23xSRlQNs43BZYBhDnrwNaZsjzCjObbWazV69encvii4jsd3IaFNx9u7sfB7QDegPHZEoW/2e6KvDdJrg/7O693L1X69ata66wIiJSO08fuftaYCZwMtDMzFLvcWgHLI/DZUB7gDi/KfBxbZRPRESCXD591NrMmsXhhsCXgfnAX4GhMdmlwLQ4/EwcJ87/i7vvdqUgIiK5k8s3rx0GPGZmRYTgM8ndf29m84AJZnYH8AbwaEz/KPC4mS0mXCFcmMOyiYhIBjkLCu7+FtAzw/QlhPsL5advAS7IVXlERGTP9ItmERFJKCiIiEhCQUFERBIKCiIiklBQEBGRhIKCiIgkFBRERCShoCAiIomsgoKZXWdmTSx41MxeN7Mzc104ERGpXdleKXzL3dcDZwKtgW8Cd+WsVCIikhfZBoVUt9YDgLHu/iaZu7oWEZF9WLZBodTMphOCwp/MrDGwI3fFEhGRfMi2Q7wRhPcsL3H3TWbWktCEJCIiBSTbK4Xn3f31+LIc3H0NcF/uiiUiIvlQ6ZWCmRUDBwGtzKw5O+8jNAHa5LhsIiJSy/bUfPRt4HpCAChlZ1BYDzyYw3KJiEgeVBoU3P1/gP8xs2vd/We1VCYREcmTrG40u/vPzOwUoEP6Mu4+PkflEhGRPMgqKJjZ48CRwBxge5zsgIKCiEgByfaR1F5Aibt7LgsjIiL5le0jqXOBL+SyICIikn/ZXim0AuaZ2Szgs9REdx+ck1KJiEheZBsUxuSyECIiUjdk+/TRC7kuiIiI5F+2Tx9tIDxtBHAgUB/41N2b5KpgIiJS+7K9UmicPm5m5wK9c1IiERHJm2q9jtPdpwJn1HBZREQkz7JtPjo/bfQAwu8W9JsFEZECk+3TR+ekDW8DlgJDarw0IiKSV9neU9ALdURE9gNZ3VMws3Zm9rSZrTKzlWY2xcza5bpwIiJSu7K90TwWeIbwXoW2wO/iNBERKSDZBoXW7j7W3bfFv3FA6xyWS0RE8iDboPCRmV1sZkXx72JgTS4LJiIitS/boPAt4GvAh8AKYCigm88iIgUm20dSbwcudfdPAMysBXAvIViIiEiByPZKoXsqIAC4+8dAz8oWMLP2ZvZXM5tvZu+Y2XVxegsze97MFsX/zeN0M7P7zWyxmb1lZsdXt1IiIlI92QaFA1Inb0iuFPZ0lbEN+K67HwOcDFxjZiXAzcAMd+8MzIjjAGcDnePfFcBDWddCRERqRLbNR/8NvGJmkwndW3wNuLOyBdx9BeH+A+6+wczmEx5nHQL0jckeA2YCo+L08fGVn6+aWTMzOyzmIyIitSDbXzSPN7PZhE7wDDjf3edluxIz60BobnoNODR1onf3FWZ2SEzWFliWtlhZnLZLUDCzKwhXEhx++OHZFkFERLKQ7ZUCMQhkHQhSzOxgYApwvbuvN7MKk2ZabYZyPAw8DNCrVy91yiciUoOq1XV2tsysPiEgPOnuv42TV5rZYXH+YcCqOL0MaJ+2eDtgeS7LJyIiu8pZULBwSfAoMN/df5I26xng0jh8KTAtbfol8Smkk4F1up8gIlK7sm4+qoZTgeHA22Y2J077HnAXMMnMRgD/BC6I854DBgCLgU3ox3EiIrUuZ0HB3f9G5vsEAP0ypHfgmlyVR0RE9iyn9xRERGTfoqAgIiIJBQUREUkoKIiISEJBQUREEgoKIiKSUFAQEZGEgoKIiCQUFEREJKGgICIiCQUFERFJKCiIiEhCQUFERBIKCiIiklBQEBGRhIKCiIgkFBRERCShoCAiIgkFBRERSSgoiIhIQkFBREQSCgoiIpJQUBARkYSCgoiIJBQUREQkoaAgIiIJBQUREUkoKIiISEJBQUREEgoKIiKSUFAQEZGEgoKIiCQUFEREJKGgICIiCQUFERFJKCiIiEgiZ0HBzH5lZqvMbG7atBZm9ryZLYr/m8fpZmb3m9liM3vLzI7PVblERKRi9XKY9zjgAWB82rSbgRnufpeZ3RzHRwFnA53j30nAQ/G/yP5pTNMqpl+Xm3LIfidnVwru/iLwcbnJQ4DH4vBjwLlp08d78CrQzMwOy1XZREQks9q+p3Cou68AiP8PidPbAsvS0pXFabsxsyvMbLaZzV69enVOCysisr+pKzeaLcM0z5TQ3R92917u3qt169Y5LpaIyP6ltoPCylSzUPy/Kk4vA9qnpWsHLK/lsomI7PdqOyg8A1wahy8FpqVNvyQ+hXQysC7VzCQiIrUnZ08fmdlTQF+glZmVAbcCdwGTzGwE8E/ggpj8OWAAsBjYBHwzV+USEZGK5SwouPvXK5jVL0NaB67JVVlERCQ7deVGs4iI1AEKCiIiklBQEBGRhIKCiIgkFBRERCShoCAiIgkFBRERSSgoiIhIQkFBREQSCgoiIpJQUBARkYSCgoiIJBQUREQkoaAgIiIJBQUREUkoKIiISEJBQUREEgoKIiKSUFAQEZGEgoKIiCQUFEREJFEv3wUQkTpmTNMqpl+Xm3JIXigo5EGHm5+t8jJL7xqYg5KIiOxKzUciIpJQUBARkYSCgoiIJBQUREQkoaAgIiIJBQUREUkoKIiISEK/UxCRuqOqP5wD/XiuhulKQUREEgoKIiKSUFAQEZGEgoKIiCQUFEREJKGgICIiiToVFMysv5ktNLPFZnZzvssjIrK/qTNBwcyKgAeBs4ES4OtmVpLfUomI7F/q0o/XegOL3X0JgJlNAIYA8/JaqgKjF/zkR1W3+9LiHBVkP1LlbZ7P47wO/WjP3D0nGVeVmQ0F+rv7yDg+HDjJ3f+tXLorgCvi6NHAwmqushXwUTWXresKuW5Q2PUr5LpBYddvX6rbEe7eOtOMunSlYBmm7Rax3P1h4OG9XpnZbHfvtbf51EWFXDco7PoVct2gsOtXKHWrM/cUgDKgfdp4O2B5nsoiIrJfqktB4R9AZzPraGYHAhcCz+S5TCIi+5U603zk7tvM7N+APwFFwK/c/Z0crnKvm6DqsEKuGxR2/Qq5blDY9SuIutWZG80iIpJ/dan5SERE8kxBQUREEgURFPbUPYaZNTCziXH+a2bWIW3e6Dh9oZmdFae1N7O/mtl8M3vHzK6rvdrsLgf1KzazWWb2ZqzfbbVXm93KXqN1S5tXZGZvmNnvc1+LiuWifma21MzeNrM5Zja7dmqyuxzVrZmZTTazBfHz16d2arO7HHzujo77LPW33syur70aZcnd9+k/wk3pd4FOwIHAm0BJuTRXA7+IwxcCE+NwSUzfAOgY83FOfrgAAAY1SURBVCkCDgOOj2kaA/9XPs99vH4GHBzT1AdeA04uhLqlLXcD8Gvg94V0bMZ5S4FW+apXjuv2GDAyDh8INCuk+pXL/0PCj8jyth8z/RXClULSPYa7fw6kusdIN4RwsAFMBvqZmcXpE9z9M3d/D1gM9Hb3Fe7+OoC7bwDmA21roS6Z5KJ+7u4bY/r68S8fTxzUeN0AzKwdMBB4pBbqUJmc1K+OqPG6mVkT4F+BRwHc/XN3X1sLdckk1/uuH/Cuu7+fsxpUUyEEhbbAsrTxMnY/gSdp3H0bsA5omc2y8ZKwJ+HbdD7kpH6xeWUOsAp43t3zUb9c7bufAjcBO2q+yFWSq/o5MN3MSi10+5IPuahbJ2A1MDY2/T1iZo1yU/w9yul5hXBl8VQNlrfGFEJQyKZ7jIrSVLqsmR0MTAGud/f11S7h3slJ/dx9u7sfR/jleG8zO3avSlk9NV43MxsErHL30r0tXA3I1bF5qrsfT+hR+Boz+9fqF7HaclG3esDxwEPu3hP4FMhXF/q5PK8cCAwGflPt0uVQIQSFbLrHSNKYWT2gKfBxZcuaWX1CQHjS3X+bk5JnJyf1S4mX5zOB/jVZ6Czlom6nAoPNbCnhkv8MM3siF4XPQk72nbun/q8CniY/zUq5qFsZUJZ21TqZECTyIZefu7OB1919ZQ2XuWbk+6bG3v4Rvl0sIdzQSd0Q6louzTXsekNoUhzuyq43hJaw80bseOCnBVq/1sQbeEBD4CVgUCHUrdyyfcnvjeZc7LtGQOOYphHwCqF34X2+bnHeS8DRcXgMcE+h7Lu05SYA38zXcbnHuue7ADW0AwcQnhB6F7glTvshMDgOFxMu1RYDs4BOacveEpdbCJwdp32RcLn3FjAn/g0ooPp1B96I9ZsL/Geh1K1c3n3JY1DI0b7rFE84bwLvpPIshLrF6ccBs+OxORVoXmD1OwhYAzTN53FZ2Z+6uRARkUQh3FMQEZEaoqAgIiIJBQUREUkoKIiISEJBQUREEgoKUpDMbIyZ3VhDeTUzs6vTxtuY2eSayDvmN9nMOtVUfuXynmBmnXORtxQmBQURkl+kVqQZoUdMIPyi2N2H1tB6uxJ+2LSkJvLL4CFCP1AiWVFQkIJhZrfE/uv/DBydNn2mmfWKw61iFxiY2WVm9hsz+x2hg7mDzWyGmb0e31eQ6hXzLuDI2Af+PWbWwczmxjyKzWxsTP+GmZ2elvdvzeyPZrbIzH5cQbEvAqbFZYrMbJyZzY35/XucfmTMp9TMXjKzf4nTDzWzpy28F+NNMzslQ/4vAV/eQ9ATSehAkYJgZicQuhroSTiuXwey6RSvD9Dd3T+OJ87z3H29mbUCXjWzZwidsh3roQPBVM+5KdcAuHu3eLKebmZd4rzjYnk+Axaa2c/cPb33TAh9NT2Vlr6tux8b19MsTn8YuNLdF5nZScDPgTOA+4EX3P08MysCDi5fOXffYWaLgR5Zbg/ZzykoSKE4DXja3TcBxJN5Np5394/jsAH/FXsd3UHo7vjQPSz/ReBnAO6+wMzeB1JBYYa7r4vlmQccwa5dKkN4odPqOLwE6GRmPwOeJV69AKcAvwld9QOhTx0IgeGSuO7thK6bM1kFtEFBQbKgoCCFpKI+W7axs6m0uNy8T9OGLyJ0FniCu2+NzUzl05eXqZvklM/ShreT+fO2ObUOd//EzHoAZxGuQL4GXA+sTV2lVFNxXI/IHumeghSKF4HzzKyhmTUGzkmbtxQ4IQ5XdoO4KeFdDFvjvYEj4vQNhNeyVrTeiwBis9HhhE7QsjUfOCou3wo4wN2nAD8gvBJ2PfCemV0Q01gMHAAzgKvi9KL45rJMuhA6zxPZIwUFKQgeXp86kdCj7RTCDdaUe4GrzOwVoFUl2TwJ9DKz2YQT/YKY9xrg5XgD+J5yy/wcKDKzt+P6L3P3z8jes4TeXCE0V82Mb8QbB4yO0y8CRphZqmfU1A3w64DT47pLCV02Y2bPmVmbOHwosNndV1ShTLIfUy+pInlkZg2BvxLeprY9B/n/O7De3R+t6bylMOlKQSSP3H0zcCu7v8O3pqxl58vlRfZIVwoiIpLQlYKIiCQUFEREJKGgICIiCQUFERFJKCiIiEji/wGCCkqUwLRrsQAAAABJRU5ErkJggg==\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "import numpy as np\n",
    "import matplotlib.pyplot as plt\n",
    "\n",
    "# routine to repeatedly collect run-time durations\n",
    "# of function genFunc\n",
    "def genDurationsDist(genFunc, nReps):\n",
    "    durations = np.zeros(nReps)\n",
    "    for i in np.arange(0, nReps):\n",
    "        tStart = time.time()\n",
    "        genFunc()\n",
    "        durations[i] = time.time() - tStart\n",
    "    return durations\n",
    "durations_bin = genDurationsDist(clumsyPrez.powerSet_bin, 500) # generate dist. of run-times\n",
    "                                                               # of Binary Mask ps generator \n",
    "durations_rec = genDurationsDist(clumsyPrez.powerSet_rec, 500) # generate dist. of run-times\n",
    "                                                               # of Recursive ps generator\n",
    "# Plot overlapping histograms of the two distributions\n",
    "plt.hist([durations_bin, durations_rec], label=['Bin. Mask', 'Recursive'])\n",
    "plt.title('Distribs. of clumsyPrez power set computation times')\n",
    "plt.xlabel('duration (sec.)')\n",
    "plt.ylabel('counts')\n",
    "plt.legend()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The two distributions certainly do not appear to be normally distributed. Below, we import and run the Mann-Whitney non-parametric comparison test to assess if the difference between the two reaches statistical significance."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 99,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Median Bin. Mask duration: 0.00205 sec., Median Recursive duration: 0.00461 sec.\n",
      "Mann-Whitney U statistic: 851.00, p-value: 4.75e-163\n"
     ]
    }
   ],
   "source": [
    "from scipy.stats import mannwhitneyu as mwu\n",
    "bin_med = np.median(durations_bin) # compute median duration of Bin. Mask ps durations\n",
    "rec_med = np.median(durations_rec) # compute median duration of Recursive ps durations\n",
    "print('Median Bin. Mask duration: %0.5f sec., Median Recursive duration: %0.5f sec.'\\\n",
    "      %(bin_med, rec_med))\n",
    "# Run non-parametric test to determine if differences between \n",
    "# distributions are statistically significant\n",
    "stat, pval = mwu(durations_bin, durations_rec)\n",
    "print('Mann-Whitney U statistic: %0.2f, p-value: %0.2e'%(stat, pval))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Measuring the time elapsed for each of the two approaches, we find that, on average, our recursive algorithm does indeed take about twice the time to complete on our machine as the binary-mask method (461 ms versus 205 ms, U = 851., p < 0.01). Of course, ours is certainly not a very controlled comparison; so please take the result with \"a grain of salt\" if you will."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Summary\n",
    "\n",
    "In part one we discussed power sets and their relation to the binary theorem. After some proding, we discovered that Python's `set()` class could not accomodate our need to include sets within sets. To solve the problem, we introduced a custom container class with a set-valued attribute, whose instances are \"hashable\" and thus, eligible for membership in `set` objects.\n",
    "\n",
    "Starting with the container strategy from part one, in part two we expanded our custom class, `ModSet()`, to include methods that perform copying, nesting, uniqueness-filtering, set-union and set-difference operations as well as others.  Several of these additional methods would prove necessary for both methods of power set generation to follow.\n",
    "\n",
    "In part three, we realized our goal of generating power sets. First, we detailed program flow of both the Binary Mask and Recursive approaches of power set generation. The mask routine used list indexing and took more lines of code than recursive method, but called fewer class methods.  The Recursive approach was shorter in terms of lines of code because it incorporated more sibling methods of the `ModSet()` class. Explaining its program flow was \"interesting\" to the least; with effort on the part of the reader, it might strengthen understanding of recursive algorithms. Without effort, it has potential to confuse.  Finally, we compared relative run times of the two approaches. It turned out that, as expected, the Binary Mask routine took less time to run than its recursive counterpart."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Sources (part 3)\n",
    "\n",
    "2. D. Van Dalen; H. C. Doets; H. De Swart (9 May 2014). [Sets: Naïve, Axiomatic and Applied: A Basic Compendium with Exercises for Use in Set Theory for Non Logicians, Working and Teaching Mathematicians and Students](https://books.google.com/books?id=PfbiBQAAQBAJ&pg=PA1#v=onepage&q&f=false). Elsevier Science. ISBN 978-1-4831-5039-0.\n",
    "\n",
    "3. [Recursion (computer science), Recursion versus Iteration](https://en.wikipedia.org/wiki/Recursion_(computer_science)#Recursion_versus_iteration),  Wikipedia."
   ]
  },
  {
   "cell_type": "raw",
   "metadata": {},
   "source": [
    "<a rel=\"license\" href=\"http://creativecommons.org/licenses/by/4.0/\"><img alt=\"Creative Commons License\" style=\"border-width:0\" src=\"https://i.creativecommons.org/l/by/4.0/88x31.png\" /></a><br /><span xmlns:dct=\"http://purl.org/dc/terms/\" property=\"dct:title\">The ModSet() class</span> by <a xmlns:cc=\"http://creativecommons.org/ns#\" href=\"nullexit.org\" property=\"cc:attributionName\" rel=\"cc:attributionURL\">nullexit.org</a> is licensed under a <a rel=\"license\" href=\"http://creativecommons.org/licenses/by/4.0/\">Creative Commons Attribution 4.0 International License</a>."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 64,
   "metadata": {},
   "outputs": [],
   "source": [
    "class ModSet():\n",
    "    \n",
    "    # Instance constructor\n",
    "    def __init__(self, setElement):\n",
    "        self.val = setElement  # set arg saved in .val attribute\n",
    "    \n",
    "    # String eval representation of self instance \n",
    "    def __repr__(self):\n",
    "        return self.val.__repr__() # Return string eval represent.\n",
    "                                   # of string object in .val\n",
    "    \n",
    "    # Method to make a copy of self instance\n",
    "    def __copy__(self):\n",
    "        return ModSet(self.val)\n",
    "    \n",
    "    # Modify .val to contain the set of itself, of itself, ...\n",
    "    # nesting .val \"depth\" number of levels.\n",
    "    def pushDown(self, depth):\n",
    "        while depth > 0:\n",
    "            self.val = set([ModSet(self.val)])\n",
    "            depth -= 1     \n",
    "    \n",
    "    # Remove one nesting level from set in self.val.\n",
    "    # If un-nested, ignore.\n",
    "    def pullUpOneLevel(self):\n",
    "        listSet = list(self.val)\n",
    "        if len(listSet) == 1:\n",
    "            self.val = listSet[0].val\n",
    "        else:\n",
    "            pass\n",
    "    \n",
    "    # Remove \"height\" nesting levels from set in\n",
    "    # self.val by repeatedly calling above method\n",
    "    def pullUp(self, height):\n",
    "        while height > 0:\n",
    "            self.pullUpOneLevel()\n",
    "            height -= 1\n",
    "    \n",
    "    # Within a single set, multiple ModSets with \n",
    "    # equivalent .val attributes can exist.  \n",
    "    # This can occur because each instance of ModSet\n",
    "    # allocated its own location in memory. For sets\n",
    "    # to have unique members in terms of ModSet.val\n",
    "    # values, we define the following filtering method.\n",
    "    def removeDuplicates(self):\n",
    "        uniqueSet = set()  # initialize as empty the unique set to be built\n",
    "        for s in self.val:  # s is a member of the ModSet().val set\n",
    "            inUniqueSet = False  # initialize match detetion flag as false\n",
    "            sTest = s  # default conditional testing value for s\n",
    "            for us in uniqueSet: # us is a member of the uniqueSet set\n",
    "                usTest = us  # default conditional testing value for us\n",
    "                if isinstance(us, ModSet): # if member us is a ModSet\n",
    "                    usTest = us.val        # change testing value to its attribute\n",
    "                if isinstance(s, ModSet):  # if member s is a ModSet\n",
    "                    sTest = s.val          # change testing value to its attribute\n",
    "                if usTest == sTest:  # compare us and s testing values on this run\n",
    "                    inUniqueSet = True  # if match, set existence flag to true\n",
    "            if not inUniqueSet:    # only add member s to uniqueSet if\n",
    "                uniqueSet.add(s)   # match is NOT detected\n",
    "        self.val = uniqueSet    # set .val to the uniqueSet from above\n",
    "    \n",
    "    # union join multiple items, enforce that ModSet members be unique\n",
    "    def union(self, *modSets):\n",
    "        for modSet in modSets:\n",
    "            self.val = self.val.union(modSet.val)  # this is union method from set class\n",
    "            self.removeDuplicates()  # removes duplicate-valued instances of ModSet members\n",
    "    \n",
    "    # set intersect multiple items\n",
    "    def intersection(self, *modSets):\n",
    "        for modSet in modSets:\n",
    "            self.val = self.val.intersection(modSet.val)\n",
    "    \n",
    "    # set difference multiple items. note: arg order matters here! \n",
    "    def difference(self, *modSets):\n",
    "        for modSet in modSets:\n",
    "            self.val = self.val.difference(modSet.val)\n",
    "    \n",
    "    # version of above method that returns a new instance,\n",
    "    # only takes two arguments.\n",
    "    def diffFunc(modSet1, modSet2):\n",
    "        return ModSet(set.difference(modSet1.val, modSet2.val))\n",
    "    \n",
    "    # Generate powerset via direct, binary mask approach\n",
    "    def powerSet_bin(self):\n",
    "        \n",
    "        ## Initialize local variables ##\n",
    "        S = list(self.val)         # convert to list for indexing\n",
    "        setSize = len(self.val)    # count number of members in source set\n",
    "        psetSize = pow(2, setSize) # calculate the number of elements in the power set\n",
    "        lastIndex = setSize - 1    # index value of last member\n",
    "        setIndices = range(0, setSize)  # make indices list for source set\n",
    "        psetIndices = range(0, psetSize) # make indices list for power set to be built\n",
    "        bMasks = [[False for s in setIndices] for p in psetIndices] # Initialize binary mask       \n",
    "        pSet = ModSet(set())  # initialize power set as empty ModSet() instance\n",
    "        pSet.pushDown(1)  # and nest it down one level for later joining\n",
    "        \n",
    "        ## Populate powerset with each subset, one at a time ##\n",
    "        for i in psetIndices: # loop through each member of power set\n",
    "            \n",
    "            ## Generate binary mask for subset i of power set ##\n",
    "            diff = i  # assign current pSet index as initial bit-flip threshold\n",
    "            for j in setIndices: # loop through each digit of mask\n",
    "                \n",
    "                if (diff >= pow(2, lastIndex - j)): # if threshold >= highest digit, then\n",
    "                    bMasks[i][lastIndex - j] = True  # set corresp. mask digit to \"true\"\n",
    "                    diff -= pow(2, lastIndex - j)   # reduce threshold for next mask digit\n",
    "                    \n",
    "            ## Form subset i of power set ##\n",
    "            # Use generator expression for compactness\n",
    "            dummySet = ModSet(set([S[k] for k in setIndices if bMasks[i][k] == True]))\n",
    "            dummySet.pushDown(1)  # nest ModSet instance down one level for union join\n",
    "            pSet.union(dummySet)  # include new subset in power set\n",
    "            \n",
    "        return pSet, bMasks  # return complete power set and binary masks as output\n",
    "    \n",
    "    # Generate powerset recursively.\n",
    "    def powerSet_rec(self):\n",
    "        \n",
    "        pSet = self.__copy__()      # Preserve self instance; its copy, pSet\n",
    "                                    # will be altered\n",
    "        pSet.pushDown(1)            # Nest pSet for later joining.\n",
    "              \n",
    "        if len(self.val) > 0:       # Recursion termination condition\n",
    "            for elSet in self.val:  # Iterate through members of set self.val\n",
    "                # Generate subset that remains after removing current\n",
    "                # element, elSet, from set self.val\n",
    "                dummySet = self.diffFunc(ModSet(set([elSet]))) \n",
    "                # To current powerset, append the powerset of the\n",
    "                # subset from previous step\n",
    "                pSet.union(dummySet.powerSet_rec())  # Self-call powerset method,\n",
    "                                                     # union join powerset of \n",
    "                                                     # dummySet with pSet\n",
    "            return pSet             # Return powerset at current \n",
    "                                    # level of recursion\n",
    "        else:\n",
    "            dummySet = ModSet(set())  # Generate instance of ModSet of empty set\n",
    "            dummySet.pushDown(1)      # Nest empty set down one level so it can\n",
    "            return dummySet           # be union joined in the recursion level\n",
    "                                      # above that called this run-through."
   ]
  }
 ],
 "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.7.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}