Feedback on Sets, and Partitions

[Anton Vredegoor]

eadorio at yahoo.com (Ernie) wrote:

>I have an implementation done  in python, not using sets but rather an
>array of integers which can be used for indexing, for processing
>equivalences and set partitions (See
>http://www.geocities.com/eadorio/equiv.pdf).

Thanks.

Here's something I wrote in 2000. I just did some very superficial
inspection of the code and adapted a few names that would not be ok
anymore, now that we have sets, but very likely I would do things very
differently now.

It might start off other implementations though so I'm providing it
below here.

# SetPart.py : return a set divided into subsets. The possible ways
# this can be done are indexed. Algorithms are adapted from the book
# "Combinatorial Algorithms..." (1999) by Donald Kreher and 
# Douglas Stinson.
# See also: http://www.math.mtu.edu/~kreher/cages.html
# Translated and adapted for Python by Anton Vredegoor:
# anton at vredegoor.doge.nl 19 jun 2000
# last update: april 2004

class SetPart:

    def __init__(self, aset):
        self.aset = aset
        self.m = len(self.aset)
        self.d = self.GeneralizedRGF(self.m)
        self.count = self.d[self.m][0]
 
    def __getitem__(self, index):
        # Partition number index
        if index > self.count - 1:
             raise IndexError 
        rgf =  self.UnrankRGF(self.m, index)
        result = self.RGFToSetPart(self.m, rgf, self.aset)
        return result[1:]

## **  Algorithm 3.12
    def RGFToSetPart(self, m, b, aset):
        # Transform a restricted growth function list into a partition
        A = []
        n = 1
        for i in range(1,m+1):
            if b[i] > n:
                n = b[i]
        for i in range(n+1):
            A.append([])
        for i in range(1,m+1):
            A[b[i]].append(aset[i-1])
        return A
            
## **  Algorithm 3.14
    def GeneralizedRGF(self, m):
        # Compute the values d[i.j]
        d = [[1L] * (m+1) for i in range(m+1)]
        for i in range(1,m+1):
            for j in range(0,m-i+1):
                d[i][j] = j * d[i-1][j] + d[i-1][j+1]
        return d

##**  Algorithm 3.16    
    def UnrankRGF(self, m, r):
        # Unrank a restricted grow function
        f = [1] * (m+1)
        j = 1
        d = self.d
        for i in range(2,m+1):
            v = d[m-i][j]
            cr = j*v
            if cr <= r:
                f[i] = j + 1
                r -= cr
                j += 1
            else:
                f[i] = r / v + 1
                r  %= v
        return f

def test():
    aset = range(5)
    P = SetPart(aset)
    print P.count
    for x in P:
         print x

if __name__ == '__main__':
    test()

Anton