Power sets in Python: an object-oriented approach (part 2)

Power sets in Python: an object-oriented approach

Overview

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” (Bernstein, M). 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.

Define a set container class

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.

In [ ]:
class ModSet():
    
    # Instance constructor
    def __init__(self, setElement):
        self.val = setElement  # set arg saved in .val attribute
    
    # String eval representation of self instance 
    def __repr__(self):
        return self.val.__repr__() # Return string eval represent.
                                   # of string object in .val
    
    # Method to make a copy of self instance
    def __copy__(self):
        return ModSet(self.val)
    
    # Modify .val to contain the set of itself, of itself, ...
    # nesting .val "depth" number of levels.
    def pushDown(self, depth):
        while depth > 0:
            self.val = set([ModSet(self.val)])
            depth -= 1     
    
    # Remove one nesting level from set in self.val.
    # If un-nested, ignore.
    def pullUpOneLevel(self):
        listSet = list(self.val)
        if len(listSet) == 1:
            self.val = listSet[0].val
        else:
            pass
    
    # Remove height number of nesting levels from set in
    # self.val by repeatedly calling above method
    def pullUp(self, height):
        while height > 0:
            self.pullUpOneLevel()
            height -= 1
                

Testing these, let’s define a set of mixed immutables and nest it three levels deep.

In [2]:
worldlyPrez = ModSet(set([('televised', 'summit'), 'DMZ', 12.6, 2019, '\"bromance\"']))
worldlyPrez.pushDown(3)
worldlyPrez
Out[2]:
{{{{2019, ('televised', 'summit'), 12.6, '"bromance"', 'DMZ'}}}}

Raising that result back up three levels should return the set to how it was originally defined.

In [3]:
worldlyPrez.pullUp(3)
worldlyPrez
Out[3]:
{2019, ('televised', 'summit'), 12.6, '"bromance"', 'DMZ'}

If you instruct to pull up greater than the set is deep, the extra ascents are ignored.

In [4]:
worldlyPrez.pullUp(2)
worldlyPrez
Out[4]:
{2019, ('televised', 'summit'), 12.6, '"bromance"', 'DMZ'}

Enforcing uniqueness

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.

In [ ]:
class ModSet():
    .
    .
    .
    def removeDuplicates(self):
        uniqueSet = set()  # initialize as empty the unique set to be built
        for s in self.val:  # s is a member of the ModSet().val set
            inUniqueSet = False  # initialize match detection flag as false
            sTest = s  # default conditional testing value for s
            for us in uniqueSet: # us is a member of the uniqueSet set
                usTest = us  # default conditional testing value for us
                if isinstance(us, ModSet): # if member us is a ModSet
                    usTest = us.val        # change testing value to its attribute
                if isinstance(s, ModSet):  # if member s is a ModSet
                    sTest = s.val          # change testing value to its attribute
                if usTest == sTest:  # compare us and s testing values on this run
                    inUniqueSet = True  # if match, set existence flag to true
            if not inUniqueSet:    # only add member s to uniqueSet if
                uniqueSet.add(s)   # match is NOT detected
        self.val = uniqueSet    # set .val to the uniqueSet from above

Testing the uniqness enforcement method

After we added removeDuplicates() to our class definition, we can test it as follows.

In [5]:
prez1 = ModSet(set([('televised', 'summit'), 'DMZ', 12.6, 2019, '\"bromance\"']))  # inst. 1
prez2 = ModSet(set([('televised', 'summit'), 'DMZ', 12.6, 2019, '\"bromance\"']))  # inst. 2
prez3 = ModSet(set([('televised', 'summit'), 'DMZ', 12.6, 2019, '\"bromance\"']))  # inst. 3
print(set([id(prez1), id(prez2), id(prez3)]))  # each instance held in its own memory block

modSetOfPrez = ModSet(set([prez1, prez2, prez3]))  # define a ModSet of ModSet instances
print(modSetOfPrez.val)  # set class sees each instance as unique though they contain 
                         # equivalent values in their attributes
{140213840135112, 140213840135280, 140213840134832}
{{2019, ('televised', 'summit'), 12.6, '"bromance"', 'DMZ'}, {2019, ('televised', 'summit'), 12.6, '"bromance"', 'DMZ'}, {2019, ('televised', 'summit'), 12.6, '"bromance"', 'DMZ'}}

Now let’s call our uniqueness filter. Only one member should remain.

In [6]:
modSetOfPrez.removeDuplicates()  # enforce uniqueness according to attribute value
print(modSetOfPrez)   # result after applying removeDuplicates()
{{2019, ('televised', 'summit'), 12.6, '"bromance"', 'DMZ'}}

Set operator methods

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.

In [ ]:
class ModSet():
    .
    .
    .
    # union-join multiple items, enforce that ModSet members be unique
    def union(self, *modSets):
        for modSet in modSets:
            self.val = self.val.union(modSet.val)  # this is union method from set class
            self.removeDuplicates()  # removes duplicate-valued instances of ModSet members
    
    # take set intersection of multiple items
    def intersection(self, *modSets):
        for modSet in modSets:
            self.val = self.val.intersection(modSet.val) # method from set class
    
    # take set difference of multiple items. Note: arg order matters here! 
    def difference(self, *modSets):
        for modSet in modSets:
            self.val = self.val.difference(modSet.val) # method from set class
    
    # version of above method that returns a new instance for assignment.
    # Note: only two arguments here.
    def diffFunc(modSet1, modSet2):
        return ModSet(set.difference(modSet1.val, modSet2.val))

Testing ModSet union

With the set operation methods now included in the class, let’s test union-joining of non-ModSet objects.

In [7]:
charges = ModSet(set())
charge1 = ModSet(set(['obstruction', 'of', 'Congress']))
charge2 = ModSet(set(['abuse', 'of', 'power']))
charge3 = ModSet(set(['incitement', 'of', 'insurrection']))

charges.union(charge1, charge2, charge3)
print(charges)
{'power', 'Congress', 'abuse', 'insurrection', 'obstruction', 'incitement', 'of'}

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.

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.

In [8]:
charge1.pushDown(1)
charge2.pushDown(1)
charge3.pushDown(1)

charges.union(charge1, charge1, charge2, charge3, ModSet(set(['all', 'fake', 'news'])))
print(charges)
{'power', 'fake', 'news', 'Congress', {'power', 'of', 'abuse'}, 'abuse', 'insurrection', {'insurrection', 'incitement', 'of'}, 'all', {'Congress', 'of', 'obstruction'}, 'obstruction', 'incitement', 'of'}

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

Testing ModSet intersection

In [9]:
claim1 = ModSet(set(['rounding', 'the', 'bend']))  # define a new instance of ModSet
claim2 = ModSet(set(['dems', 'stole', 'the', 'election'])) # define another new instance
claim1.union(charge1, charge2)  # union-join charges 1 and 2 from above with claim1 
claim2.union(charge2, charge3)  # union-join charges 2 and 3 from above with claim2
claim1.intersection(claim2)  # perform set-intersection of claims 1 and 2
claim1  # output the post-intersection result
Out[9]:
{{'power', 'of', 'abuse'}, 'the'}

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.

Testing ModSet set-difference

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

In [10]:
charges.difference(charge2)
charges
Out[10]:
{'power', 'fake', 'news', 'Congress', 'abuse', 'insurrection', {'insurrection', 'incitement', 'of'}, 'all', {'Congress', 'of', 'obstruction'}, 'obstruction', 'incitement', 'of'}

leaves charges with all but the {'abuse', 'of', 'power'} member in the result. So, check.

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 unchanged. To test .diffFunc(), we’ll now attempt to remove charge1 from charges (since charge2 has already been removed in the previous step).

In [11]:
chargesReduced = ModSet.diffFunc(charges, charge1)
chargesReduced
Out[11]:
{'power', 'fake', 'news', 'Congress', 'abuse', 'insurrection', {'insurrection', 'incitement', 'of'}, 'all', 'obstruction', 'incitement', 'of'}

You can see that the value from charge1, {'obstruction', 'of', 'Congress'}, is absent from chargesReduced, though all others from its parent, charges, are present.

Lastly, let’s examine charges to make sure that this particular instance has not been modified since last step.

In [12]:
charges
Out[12]:
{'power', 'fake', 'news', 'Congress', 'abuse', 'insurrection', {'insurrection', 'incitement', 'of'}, 'all', {'Congress', 'of', 'obstruction'}, 'obstruction', 'incitement', 'of'}

And there the charge remains, in all its glory, one could say…

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 power sets. We’ll do this in part three to come.

Sources (part 2)

1. Bernstein, M. Recursive Python Objects, https://bernsteinbear.com/blog. 2019.

Get ModSet()

The above code comprises the core of our ModSet() class. We’ll walk-through the power set generating methods in part three. You can download ModSet()‘s complete definition from github: modset.py

Creative Commons License
The ModSet() class by nullexit.org is licensed under a Creative Commons Attribution 4.0 International License.