440,772 Members | 935 Online Need help? Post your question and get tips & solutions from a community of 440,772 IT Pros & Developers. It's quick & easy.

# Feedback on Sets, and Partitions

7 Replies

 P: n/a In article , "Steve" wrote: For my current project, I need to generate partitions of sets up to size 25. I am rather hopeless it will ever be feasible, and I have begun looking for a different approach. Thanks for any replies! There are 4638590332229999353 partitions of an 25 item set. So, I think generating them all is a little out of the question. -- David Eppstein http://www.ics.uci.edu/~eppstein/ Univ. of California, Irvine, School of Information & Computer Science Jul 18 '05 #2

 P: n/a In article , David Eppstein wrote: In article , "Steve" wrote: For my current project, I need to generate partitions of sets up to size 25. I am rather hopeless it will ever be feasible, and I have begun looking for a different approach. Thanks for any replies! There are 4638590332229999353 partitions of an 25 item set. So, I think generating them all is a little out of the question. BTW, here is some code for generating these numbers. I think it's a little interesting that one can write the obvious one-line definition for factorials, forgetting the base case, and then make it work anyway via the magic of memoization. Something to think about in connection with PEP 318... def memoize(recurrence, base_case={}): memo = {} for k,rk in base_case.items(): if not isinstance(k,tuple): k = (k,) memo[k] = rk def memoized(*args): if args not in memo: memo[args] = recurrence(*args) return memo[args] return memoized def factorial(n): return factorial(n-1)*n factorial = memoize(factorial, base_case={0:1}) def choose(n,k): return factorial(n) // factorial(k) // factorial(n-k) def bell(n): return sum([choose(n-1,k)*bell(n-1-k) for k in range(n)]) bell = memoize(bell, base_case={0:1}) print "There are",bell(25),"partitions of a 25 item set." -- David Eppstein http://www.ics.uci.edu/~eppstein/ Univ. of California, Irvine, School of Information & Computer Science Jul 18 '05 #3

 P: n/a "Steve" wrote in message news:... This post has two parts. First is my feedback on sets. (Hello? Last summer called, they want their discussion thread back...) Second is some questions about my implementation of a partition function for sets. Part 1. --- ..... snipped Part 2 --- ..... snipped For my current project, I need to generate partitions of sets up to size 25. I am rather hopeless it will ever be feasible, and I have begun looking for a different approach. Thanks for any replies! For Part 2, Google on restricted growth functions if you are interested in non-recursive generation of set partitions of n objects with k classes. 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). Regards, Ernie Jul 18 '05 #4

 P: n/a David Eppstein wrote: BTW, here is some code for generating these numbers. I think it's alittle interesting that one can write the obvious one-line definitionfor factorials, forgetting the base case, and then make it work anywayvia the magic of memoization. Something to think about in connectionwith PEP 318... [snip some interesting code] Here's a more tedious way to do the same, but this code is more "graphic" in that it shows how one can build up a triangle of numbers line by line according to some mutation prescription. Depending on the kind of prescription one ends up with pascals triangle or the triangle for bell numbers. def pascal_mutate(L): R = [L[i] + L[i+1] for i in xrange(len(L)-1)] return  + R +  def stirling_mutate(L): R = [L[i] + (i+2)*L[i+1] for i in xrange(len(L)-1)] return  + R +  def triangle(mutator): L =  while 1: yield L L = mutator(L) def listify(gen): cache = [] def func(n): while len(cache) <= n: cache.append(gen.next()) return cache[n] return func def triangle_function_generator(mutator): T = listify(triangle(mutator)) def func(n,k): return T(n)[k] return func pascal = triangle_function_generator(pascal_mutate) stirling_raw = triangle_function_generator(stirling_mutate) def noverk(n,k): return reduce(lambda a,b: a*(n-b)/(b+1),range(k),1) def stirling(n,k): return stirling_raw(n-1,k-1) def bell(n): return sum([stirling(n,i) for i in range(1,n+1)]) def test(): n,k = 10,4 assert pascal(n,k) == noverk(n,k) print bell(25) if __name__=='__main__': test() #prints 4638590332229999353 Anton Jul 18 '05 #5

 P: n/a "Steve" wrote in message news:... Another unintutive feature is that there can be multiple sets with the same members. I.e., you can have sets A and B such that "A == B" is true and "A is B" is false. I would like more information on the reasons for this choice and whether there would be anything to gain or lose by having "A == B" entail "A is B". I can't speak for the designers, but I think there's two problems with A == B => A is B. One, none of the other sequences behave that way. Two (and this is the real killer) I think it would be tough to implement. A = Set([1, 2, 3]) B = Set([1, 2]) #A is B clearly false, as is A==B B.add(3) #Now A==B is true After every alteration of a set, such as the add() above, you'd have to do an exhaustive comparison of every other set for equality. Then you'd do something like B = A to drop the old B set and set up another reference to A. Then if you altered B and not A, you'd have to do something like copy A, make the change, and assign the result to B. Problem with that is, it breaks the case where you want A and B to be pointing to a single set which is modified so that A and B change. The most common case would be passing a Set to a subroutine. So I just don't think it's feasible. Jul 18 '05 #6

 P: n/a > I could live with only immutable sets, but it is nice being able to use: myset.add(x) instead of: newmyset = myset | Set([x]) What about myset |= Set([x]) Presumably that would work analogously to += for strings. Another unintutive feature is that there can be multiple sets with the same members. I.e., you can have sets A and B such that "A == B" is true and "A is B" is false. Why is that any more unintuitive than the fact that there can be multiple integers with the same value? For example: x = 12345 y = 12344+1 After these two statements, most Python implementations will evaluat "x is y" as false, but of course 1==y is true. Jul 18 '05 #7

 P: n/a ea*****@yahoo.com (Ernie) wrote: I have an implementation done in python, not using sets but rather anarray of integers which can be used for indexing, for processingequivalences and set partitions (Seehttp://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: # an***@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] 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 =  * (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 Jul 18 '05 #8

### This discussion thread is closed

Replies have been disabled for this discussion. 