set partitions iterator not working?

[Dan Drake]

Hello,

I'm doing some work with complete matchings, and I'm dealing with them
as set partitions. I just need to iterate over matchings, not make
lists, so it seems like I shouldn't run out of memory (I have 1.5 gigs
installed), but I am. I'm using Sage 2.10.1 on Linux.

If I do something like the following, memory usage climbs and climbs:

n = 0
for m in SetPartitions(range(16), [2, 2, 2, 2, 2, 2, 2, 2]):
n += 1

This seems weird, since there's a set partitions iterator, and it
shouldn't take a lot of memory.

On the other hand, here's an iterator for complete matchings that I
wrote that works just fine:

def matchings(n):
for m in matchingsset(range(1, n+1)): yield m

def matchingsset(L):
if len(L) == 0:
yield []
else:
for k in range(1,len(L)):
for m in matchingsset(L[1:k] + L[k+1:]):
yield m + [[L[0], L[k]]]
return

Now running the same counting loop works, with no extra memory usage:

n = 0
for m in matchings(16):
n += 1

Sage seems to have an iterator for set partitions; it is working? Do I
need to use something else to get a memory-efficient iterator?

Thanks for the help,

Dan

--
--- Dan Drake <dr...@mathsci.kaist.ac.kr>
----- KAIST Department of Mathematical Sciences
------- http://math.kaist.ac.kr/~drake

[Mike Hansen]

Hi Dan,

Thanks for pointing this out. There was a bug in a part of the
iterator that was making lists of things. I've made this ticket #2139
( http://trac.sagemath.org/sage_trac/ticket/2139 ) and posted a patch
which fixes the issue.

--Mike

> -----BEGIN PGP SIGNATURE-----
> Version: GnuPG v1.4.6 (GNU/Linux)
>
> iD8DBQFHr+TZr4V8SljC5LoRAhO7AKC31YwU7kom+K7SvjO1pJfgx/vc+wCgpqKi
> CrVAbJ5zgxUb7LjHEtTpRn8=
> =4LDm
> -----END PGP SIGNATURE-----
>
>