More user feedback on Sets.py

[David Eppstein]

In article <eppstein-310496.15201409112003 at news.service.uci.edu>,
 David Eppstein <eppstein at ics.uci.edu> wrote:

> I am a little concerned that "powerset" is not the right name, because 
> its output is a sequence not a set, but can't think of a better.

New name: "finitesets" since it is not truly the powerset of an infinite 
set -- it does not include the infinite subsets.  Here's an example of 
sets of sets in code I was using for creating a certain combinatorial 
representation of families of weak orders: each dichotomy is a set, and 
each state is a set of mutually comparable dichotomies.  As before with 
the graph examples, sets of sets are useful but the automatic 
immutabilization protocol isn't.

One more thing that would be useful in the set package, although it's 
easy enough to roll your own: a "singleton" function that converts a 
single item to an (immutable) set.  I don't find continually having to 
write ImmutableSet([expression]) to be very readable; for instance, it 
isn't obvious from that syntax that there's only one thing in the 
expression.

After:
    def singleton(x):
        """One-element set containing x."""
        return ImmutableSet([x])
        
    def finitesets(U):
        """Generates all finite subsets of a set or sequence U."""
        U = iter(U)
        yield ImmutableSet()
        x = singleton(U.next())
        yield x
        it = finitesets(U)
        it.next()   # skip empty set, already generated
        for S in it:
            yield S
            yield S | x        
    
    class weak(medium):
        """weak orders on an n-element set"""
        
        def __init__(self, n):
            self.initialState = ImmutableSet()
            dichotomies = [S for S in finitesets(range(n)) if 0<len(S)<n]
            self.tokens = [(self.add,o) for o in dichotomies] + \
                          [(self.remove,o) for o in dichotomies]
        
        def transition(self, state, token):
            op,dichotomy = token
            return op(state,dichotomy)
            
        def add(self,state,dichotomy):
            for x in state:
                if not x < dichotomy and not x > dichotomy:
                    return state
            return state | singleton(dichotomy)
        
        def remove(self,state,dichotomy):
            return state - singleton(dichotomy)

Before:
    class weakOrder(tuple):
        """Representation of weak order medium state.
        We represent a weak order as a sorted sequence of integers,
        representing masks for binary splits.
        The nonzero bits of each integer must be a superset of the
        bits in the previous integer.  The last item in the sequence
        is an integer with all bits set.
        """
    
        def split(self,mask):
            """Attempt to add the mask to our sorted sequence."""
            for i in range(len(self)):
                if self[i] >= mask:
                    break
                if self[i] & mask != self[i]:
                    return self
            if self[i] == mask or self[i] & mask != mask:
                return self
            return weakOrder(self[:i] + (mask,) + self[i:])
                    
        def join(self,mask):
            """Attempt to remove the mask from our sorted sequence."""
            if mask not in self:
                return self
            i = list(self).index(mask)
            return weakOrder(self[:i] + self[i+1:])

    class weak(medium):
        """weak orders on an n-element set"""
        
        def __init__(self, n):
            everything = (1<<n) - 1
            self.initialState = weakOrder((everything,))
            positive = range(1,everything)
            self.tokens = [-x for x in positive] + positive
        
        def transition(self, state, token):
            if token > 0:
                return state.split(token)
            else:
                return state.join(-token)

-- 
David Eppstein                      http://www.ics.uci.edu/~eppstein/
Univ. of California, Irvine, School of Information & Computer Science