# Feedback on Sets, and Partitions

Anton Vredegoor anton at vredegoor.doge.nl
Fri Apr 30 20:33:32 CEST 2004

```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

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.
# 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

```