Re: Pulling all n-sized combinations from a list
[EMAIL PROTECTED] wrote:
hi,
I'm not sure why this hasn't come up yet, but this seems to beg for
list comprehensions, if not generator expressions. All of the
following run in under 2 seconds on my old laptop:
alph = 'abcdefghijklmnopqrstuvwxyz'
len([''.join((a,b,c,d)) for a in alph for b in alph for c in alph for d
in alph])
456976
len([''.join((a,b,c,d)) for a in alph for b in alph for c in alph for d
in alph
... if (a=b and b=c and c=d)])
23751
len([''.join((a,b,c,d)) for a in alph for b in alph for c in alph for d
in alph
... if (a!=b and b!=c and c!=d and d!=a and b!=d and a!=c)])
358800
len([''.join((a,b,c,d)) for a in alph for b in alph for c in alph for d
in alph
... if (ab and bc and cd)])
14950
Well, _I_ was using them in my original program to create the
conditionals, but not for the loops. So if we combine your idea
to use list comprehensions for the loop with my list comprehensions
of the conditionals, we aren't limited to asking for only 4-letter
words.
And it runs faster than my original.
Thanks.
def ooloop6(a, n, perm=True, repl=True):
if (not repl) and (nlen(a)): return
r0 = range(n)
r1 = r0[1:]
if perm and repl: # ok
v = ','.join(['c%s' % i for i in r0])
f = ' '.join(['for c%s in a' % i for i in r0])
e = ''.join([p = [''.join((,v,)) ,f,]])
exec e
return p
if (not perm) and repl:# ok
v = ','.join(['c%s' % i for i in r0])
f = ' '.join(['for c%s in a' % i for i in r0])
i = ' and '.join(['(c%s=c%s)' % (j,j-1) for j in r1])
e = ''.join([p = [''.join((,v,)) ,f, if ,i,]])
exec e
return p
if perm and (not repl):# ok
v = ','.join(['c%s' % i for i in r0])
f = ' '.join(['for c%s in a' % i for i in r0])
i = ' and '.join([' and '.join(['(c%s!=c%s)' % (j,k) for k in
range(j)]) for j in r1])
e = ''.join([p = [''.join((,v,)) ,f, if ,i,]])
exec e
return p
if (not perm) and (not repl): # ok
v = ','.join(['c%s' % i for i in r0])
f = ' '.join(['for c%s in a' % i for i in r0])
i = ' and '.join(['(c%sc%s)' % (j,j-1) for j in r1])
e = ''.join([p = [''.join((,v,)) ,f, if ,i,]])
exec e
return p
p = ooloop6('abcdefghijklmnopqrstuvwxyz',4,True,True)
print
print len(p)
p = ooloop6('abcdefghijklmnopqrstuvwxyz',4,False,True)
print
print len(p)
p = ooloop6('abcdefghijklmnopqrstuvwxyz',4,True,False)
print
print len(p)
p = ooloop6('abcdefghijklmnopqrstuvwxyz',4,False,False)
print
print len(p)
456976
23751
358800
14950
cheers,
Jess
--
http://mail.python.org/mailman/listinfo/python-list
Re: Pulling all n-sized combinations from a list
hi, I'm not sure why this hasn't come up yet, but this seems to beg for list comprehensions, if not generator expressions. All of the following run in under 2 seconds on my old laptop: alph = 'abcdefghijklmnopqrstuvwxyz' len([''.join((a,b,c,d)) for a in alph for b in alph for c in alph for d in alph]) 456976 len([''.join((a,b,c,d)) for a in alph for b in alph for c in alph for d in alph ... if (a=b and b=c and c=d)]) 23751 len([''.join((a,b,c,d)) for a in alph for b in alph for c in alph for d in alph ... if (a!=b and b!=c and c!=d and d!=a and b!=d and a!=c)]) 358800 len([''.join((a,b,c,d)) for a in alph for b in alph for c in alph for d in alph ... if (ab and bc and cd)]) 14950 cheers, Jess -- http://mail.python.org/mailman/listinfo/python-list
Re: Pulling all n-sized combinations from a list
[EMAIL PROTECTED] wrote: But it turns out he actually had one, which he graciously provided in response to my observation. If I had kept my trap shut, I wouldn't have it, would I? I completely agree, but you could put your questions in a way that increases your chances of helpful replies... http://www.catb.org/~esr/faqs/smart-questions.html -- http://mail.python.org/mailman/listinfo/python-list
Re: Pulling all n-sized combinations from a list
Magnus Lycka wrote: [EMAIL PROTECTED] wrote: But it turns out he actually had one, which he graciously provided in response to my observation. If I had kept my trap shut, I wouldn't have it, would I? I completely agree, but you could put your questions in a way that increases your chances of helpful replies... http://www.catb.org/~esr/faqs/smart-questions.html Ok, but I wasn't asking a question. I was answering the question why is nobody using my program?. Now, if _I_ had specifically asked how _I_ could use his program, then the snide remarks about the availability of free compilers on the Internet would have been somewhat justified. I had already given up any hope of ever running probstat, so I wasn't really looking for an answer since I was already aware of what it would take for me to compile it on Windows. It was just a lucky coincidence that by mentioning Windows, JD replied that he had a pyd available. And, strange as it may seem, asking questions the smart way is sometimes less effective than being a smartass. Given a chance to say idiot, you're wrong and here's why... people will jump all over you. Take this thread, for example. Of course, if they just call you an idiot then you haven't gained anything. But there's nobody like that on comp.lang.python, right? -- http://mail.python.org/mailman/listinfo/python-list
Re: Pulling all n-sized combinations from a list
[EMAIL PROTECTED] wrote: Magnus Lycka wrote: [EMAIL PROTECTED] wrote: But it turns out he actually had one, which he graciously provided in response to my observation. If I had kept my trap shut, I wouldn't have it, would I? [...] And, strange as it may seem, asking questions the smart way is sometimes less effective than being a smartass. Given a chance to say idiot, you're wrong and here's why... people will jump all over you. Take this thread, for example. Of course, if they just call you an idiot then you haven't gained anything. But there's nobody like that on comp.lang.python, right? Of course not, you idiot :-) regards Steve -- Steve Holden +44 150 684 7255 +1 800 494 3119 Holden Web LLC www.holdenweb.com PyCon TX 2006 www.python.org/pycon/ -- http://mail.python.org/mailman/listinfo/python-list
Re: Pulling all n-sized combinations from a list
[EMAIL PROTECTED] wrote: But using the free SDK compiler from MS? That seems elusive. Have you seen this? http://www.vrplumber.com/programming/mstoolkit/ -- http://mail.python.org/mailman/listinfo/python-list
Re: Pulling all n-sized combinations from a list
Magnus Lycka wrote: [EMAIL PROTECTED] wrote: But using the free SDK compiler from MS? That seems elusive. Have you seen this? http://www.vrplumber.com/programming/mstoolkit/ I have, although I haven't tried it as I was able to get a GMPY Windows binary from someone else. It may be that probstat is not as complicated as GMPY. So if I get some free time, I might try it, would be worth it in the long run. Thanks for pointing it out. Nevertheless, my elusive comment was certainly justified: quote Note also that the author of the document (Mike Fletcher) has abandoned Windows as a development platform (in some part because of the difficulties in getting a working compiler to support the platform), and is thus no longer actively maintaining this page. While some people are still reporting successes, others are having difficulties with building certain projects. The Toolkit approach is, in short, a bit dicey as a platform for serious development. /quote I think it's safe to say most Windows users are NOT software developers. If the professional software developers have trouble figuring it out, what chance does an inexperienced end user have? And for the record, I never implied that JD was obligated to provide a Windows binary for his project. I was merely pointing out that there are a lot of people not using his module because of the lack of a Windows binary, so it really should come as no surprise that people keep asking for solutions to combination/permutation problems. But it turns out he actually had one, which he graciously provided in response to my observation. If I had kept my trap shut, I wouldn't have it, would I? Squeaky wheels get grease. And, through my blundering tests, he found a place where he should be raising an exception, so he benefits also. Luckily, not everyone has the here's a nickel kid, get yourself a better computer attitude. -- http://mail.python.org/mailman/listinfo/python-list
Re: Pulling all n-sized combinations from a list
On Wed, Feb 08, 2006 at 12:50:19PM -0800, Swroteb wrote: Hi there, I've got a reasonably sized list of objects that I'd like to pull out all combinations of five elements from. Right now I have a way to do this that's quite slow, but manageable. I know there must be a better way to do this, but I'm not sure what it is. Here's what I've got so far: import probstat # http://probstat.sourceforge.net for (a, b, c) in probstat.Combination(range(9), 3): # 0..9, pick 3 print a, b, c It is a C extension that does permutations combinations and is about 10x faster than doing it in pure python [I'm the author]. It is also the 3rd result for python combination and 5th for python permutaiton but every month someone posts to c.l.py asking for something similar. Go figure. -jackdied -- http://mail.python.org/mailman/listinfo/python-list
Re: Pulling all n-sized combinations from a list
Jack Diederich wrote: On Wed, Feb 08, 2006 at 12:50:19PM -0800, Swroteb wrote: Hi there, I've got a reasonably sized list of objects that I'd like to pull out all combinations of five elements from. Right now I have a way to do this that's quite slow, but manageable. I know there must be a better way to do this, but I'm not sure what it is. Here's what I've got so far: import probstat # http://probstat.sourceforge.net for (a, b, c) in probstat.Combination(range(9), 3): # 0..9, pick 3 print a, b, c It is a C extension that does permutations combinations and is about 10x faster than doing it in pure python [I'm the author]. It is also the 3rd result for python combination and 5th for python permutaiton but every month someone posts to c.l.py asking for something similar. Go figure. Did you ever figure that some people use Windows? -jackdied -- http://mail.python.org/mailman/listinfo/python-list
Re: Pulling all n-sized combinations from a list
[EMAIL PROTECTED] wrote: It is a C extension that does permutations combinations and is about 10x faster than doing it in pure python [I'm the author]. It is also the 3rd result for python combination and 5th for python permutaiton but every month someone posts to c.l.py asking for something similar. Go figure. Did you ever figure that some people use Windows? Windows don't support C ? that was a new one. /F -- http://mail.python.org/mailman/listinfo/python-list
Re: Pulling all n-sized combinations from a list
On Thu, Feb 09, 2006 at 10:23:12AM -0800, [EMAIL PROTECTED] wrote: Jack Diederich wrote: On Wed, Feb 08, 2006 at 12:50:19PM -0800, Swroteb wrote: Hi there, I've got a reasonably sized list of objects that I'd like to pull out all combinations of five elements from. Right now I have a way to do this that's quite slow, but manageable. I know there must be a better way to do this, but I'm not sure what it is. Here's what I've got so far: import probstat # http://probstat.sourceforge.net for (a, b, c) in probstat.Combination(range(9), 3): # 0..9, pick 3 print a, b, c It is a C extension that does permutations combinations and is about 10x faster than doing it in pure python [I'm the author]. It is also the 3rd result for python combination and 5th for python permutaiton but every month someone posts to c.l.py asking for something similar. Go figure. Did you ever figure that some people use Windows? I don't have a windows dev box so I can't vouch for this binary but a user sent me a windows .pyd yesterday. http://jackdied.com/static/probstat.pyd -jackdied -- http://mail.python.org/mailman/listinfo/python-list
Re: Pulling all n-sized combinations from a list
Fredrik Lundh wrote: [EMAIL PROTECTED] wrote: It is a C extension that does permutations combinations and is about 10x faster than doing it in pure python [I'm the author]. It is also the 3rd result for python combination and 5th for python permutaiton but every month someone posts to c.l.py asking for something similar. Go figure. Did you ever figure that some people use Windows? Windows don't support C ? that was a new one. Windows comes with a C compiler? That's news to me. /F -- http://mail.python.org/mailman/listinfo/python-list
Re: Pulling all n-sized combinations from a list
[EMAIL PROTECTED] wrote: Fredrik Lundh wrote: [EMAIL PROTECTED] wrote: It is a C extension that does permutations combinations and is about 10x faster than doing it in pure python [I'm the author]. It is also the 3rd result for python combination and 5th for python permutaiton but every month someone posts to c.l.py asking for something similar. Go figure. Did you ever figure that some people use Windows? Windows don't support C ? that was a new one. Windows comes with a C compiler? That's news to me. if you don't have internet, how do you manage to post to this group ? /F -- http://mail.python.org/mailman/listinfo/python-list
Re: Pulling all n-sized combinations from a list
[EMAIL PROTECTED] wrote: Fredrik Lundh wrote: Windows don't support C ? that was a new one. Windows comes with a C compiler? That's news to me. It doesn't come with Python either. Both Python and the compiler etc that you need can be freely downloaded from the internet. I suggest you leave the witty sarcasms to effbot. He might be a little annoying at times, but he know what he's talking about. -- http://mail.python.org/mailman/listinfo/python-list
Re: Pulling all n-sized combinations from a list
Magnus Lycka wrote: [EMAIL PROTECTED] wrote: Fredrik Lundh wrote: Windows don't support C ? that was a new one. Windows comes with a C compiler? That's news to me. It doesn't come with Python either. Both Python and the compiler etc that you need can be freely downloaded from the internet. Just out of curiosity, have you ever tried it? I _have_ downloaded Cygwin and was able to compile GMP using gcc (after much wailing gnashing of teeth). But using the free SDK compiler from MS? That seems elusive. Lucky for me, someone who had the non-free MS compiler was able to create a Windows binary of GMPY or I'd still be SOL. If you don't have the tools or don't know how to use them, the Windows C support may as well be on the far side of the Moon for all the good it does me. I suggest you leave the witty sarcasms to effbot. I thought I was replying to a witty sarcasm. He might be a little annoying at times, but he know what he's talking about. -- http://mail.python.org/mailman/listinfo/python-list
Re: Pulling all n-sized combinations from a list
Jack Diederich wrote:
On Thu, Feb 09, 2006 at 10:23:12AM -0800, [EMAIL PROTECTED] wrote:
Jack Diederich wrote:
On Wed, Feb 08, 2006 at 12:50:19PM -0800, Swroteb wrote:
Hi there,
I've got a reasonably sized list of objects that I'd like to pull out
all combinations of five elements from. Right now I have a way to do
this that's quite slow, but manageable. I know there must be a better
way to do this, but I'm not sure what it is. Here's what I've got so
far:
import probstat # http://probstat.sourceforge.net
for (a, b, c) in probstat.Combination(range(9), 3): # 0..9, pick 3
print a, b, c
It is a C extension that does permutations combinations and is
about 10x faster than doing it in pure python [I'm the author].
It is also the 3rd result for python combination and 5th for
python permutaiton but every month someone posts to c.l.py asking
for something similar. Go figure.
Did you ever figure that some people use Windows?
I don't have a windows dev box so I can't vouch for this binary but
a user sent me a windows .pyd yesterday.
http://jackdied.com/static/probstat.pyd
-jackdied
Hey, thanks!
I have a pure Python permutation generator that generates
a Cartesian product of a string with itself with filters
to emulate
permutation w/ replacemment
combination w/ replacemment
permutation w/o replacemment
combination w/o replacemment
so I put together a little test program to see how probstat
compares. Correspondence to my emulations is (as far as I can tell)
permutation w/ replacemment: equivalent to probstat.Cartesian
combination w/ replacemment: no equivalent
permutation w/o replacemment: equivalent to probstat.Permutation
combination w/o replacemment: equivalent to probstat.Combination
Here's the test program:
-
import probstat
import time
def cxxx(m):
return '(' + ' and '.join(['(i%s!=i%s)' % (m,i) for i in range(m)])
+ ')'
def ooloop5(a, n, perm=True, repl=True):
if (not repl) and (nlen(a)): return
p = []
loop = '\n'.join([(' ' * i) + 'for i%s in a:' % i for i in range(n)])
+ '\n'
indt = ' ' * n
sub1 = indt + 'if perm and repl:\n'
sub2 = indt + 'if (not perm) and repl:\n'
ccc2 = ' and '.join(['(i%s=i%s)' % (i,i-1) for i in range(1,n)])
con2 = indt + ' if ' + ccc2 + ':\n'
sub3 = indt + 'if perm and (not repl):\n'
cccx = ' and '.join([cxxx(m) for m in range(1,n)])
con3 = indt + ' if ' + cccx + ':\n'
sub4 = indt + 'if (not perm) and (not repl):\n'
ccc4 = ' and '.join(['(i%si%s)' % (i,i-1) for i in range(1,n)])
con4 = indt + ' if ' + ccc4 + ':\n'
bod1 = indt + ' s = ' + '+'.join(['i%s' % i for i in range(n)]) + '\n'
bod2 = indt + ' p.append(s)\n'
bod3 = indt + ' s = ' + '+'.join(['i%s' % i for i in range(n)]) +
'\n'
bod4 = indt + ' p.append(s)\n'
e = loop + sub1 + bod1 + bod2 + sub2 + con2 + bod3 + bod4 + sub3 +
con3 + bod3 + bod4 + sub4 + con4 + bod3 + bod4
exec e
return p
def p_cart(a,n):
A = list(a)
c = probstat.Cartesian([A for i in range(n)])
p = []
for i in c:
p.append(''.join(i))
return p
def p_perm(a,n):
A = list(a)
t0 = time.time()
if len(A)n:
c = probstat.Permutation(A,n)
else:
c = probstat.Permutation(A)
print time.time()-t0
p = []
for i in c:
p.append(''.join(i))
return p
def p_comb(a,n):
A = list(a)
c = probstat.Combination(A,n)
p = []
for i in c:
p.append(''.join(i))
return p
print 'permutation w/ replacemment'
p = ooloop5(abc, 3, True, True)
print p
print
print 'combination w/ replacemment'
p = ooloop5(abc, 3, False, True)
print p
print
print 'permutation w/o replacemment'
p = ooloop5(abc, 3, True, False)
print p
print
print 'combination w/o replacemment'
p = ooloop5(abc, 3, False, False)
print p
print
print 'probstat.Cartesian'
p = p_cart('abc',3)
print p
print
print 'probstat.Permutation'
p = p_perm('abc',3)
print p
print
print 'probstat.Combination'
p = p_comb('abc',3)
print p
print
print 'permutation w/ replacemment abcdefghijklmnopqrstuvwxyz:4'
t0 = time.time()
p = ooloop5(abcdefghijklmnopqrstuvwxyz, 4, True, True)
t1 = time.time()
print len(p),'4-letter words',t1-t0,'seconds'
print 'combination w/ replacemment abcdefghijklmnopqrstuvwxyz:4'
t0 = time.time()
p = ooloop5(abcdefghijklmnopqrstuvwxyz, 4, False, True)
t1 = time.time()
print len(p),'4-letter words',t1-t0,'seconds'
print 'permutation w/o replacemment abcdefghijklmnopqrstuvwxyz:4'
t0 = time.time()
p = ooloop5(abcdefghijklmnopqrstuvwxyz, 4, True, False)
t1 = time.time()
print len(p),'4-letter words',t1-t0,'seconds'
print 'combination w/o replacemment abcdefghijklmnopqrstuvwxyz:4'
t0 = time.time()
p =
Re: Pulling all n-sized combinations from a list
liberally snipped out parts
On Thu, Feb 09, 2006 at 03:25:18PM -0800, [EMAIL PROTECTED] wrote:
Jack Diederich wrote:
On Wed, Feb 08, 2006 at 12:50:19PM -0800, Swroteb wrote:
I've got a reasonably sized list of objects that I'd like to pull out
all combinations of five elements from. Right now I have a way to do
this that's quite slow, but manageable. I know there must be a better
way to do this, but I'm not sure what it is. Here's what I've got so
far:
import probstat # http://probstat.sourceforge.net
for (a, b, c) in probstat.Combination(range(9), 3): # 0..9, pick 3
print a, b, c
so I put together a little test program to see how probstat
compares. Correspondence to my emulations is (as far as I can tell)
def p_perm(a,n):
A = list(a)
t0 = time.time()
if len(A)n:
c = probstat.Permutation(A,n)
else:
c = probstat.Permutation(A)
print time.time()-t0
p = []
for i in c:
p.append(''.join(i))
return p
This never calls the A choose n branch because len(A) is always
bigger than n.
print 'permutation w/o replacemment abcdefghijklmnopqrstuvwxyz:4'
t0 = time.time()
p = p_perm(abcdefghijklmnopqrstuvwxyz, 4)
t1 = time.time()
print len(p),'4-letter words',t1-t0,'seconds'
Unfortunately, the long test died (out of virtual memory) executing
the probstat.Permution test.
import probstat
p = probstat.Permutation(range(25))
len(p)
2076180480
p = probstat.Permutation(range(26))
len(p)
-1853882368
Overflow error. I'll have to add a test that raises a ValueError
for lists that are too big.
The following simple loop takes three minutes to run on my laptop
import probstat
count_to = len(probstat(range(12))) # just computes the size
cnt = 0
while cnt count_to:
cnt += 1
So a permutation of all arrangements of the alphabet would take
rougly forever.
-Jack
--
http://mail.python.org/mailman/listinfo/python-list
Re: Pulling all n-sized combinations from a list
Jack Diederich wrote:
liberally snipped out parts
On Thu, Feb 09, 2006 at 03:25:18PM -0800, [EMAIL PROTECTED] wrote:
Jack Diederich wrote:
On Wed, Feb 08, 2006 at 12:50:19PM -0800, Swroteb wrote:
I've got a reasonably sized list of objects that I'd like to pull
out
all combinations of five elements from. Right now I have a way to
do
this that's quite slow, but manageable. I know there must be a
better
way to do this, but I'm not sure what it is. Here's what I've got
so
far:
import probstat # http://probstat.sourceforge.net
for (a, b, c) in probstat.Combination(range(9), 3): # 0..9, pick 3
print a, b, c
so I put together a little test program to see how probstat
compares. Correspondence to my emulations is (as far as I can tell)
def p_perm(a,n):
A = list(a)
t0 = time.time()
if len(A)n:
c = probstat.Permutation(A,n)
else:
c = probstat.Permutation(A)
print time.time()-t0
p = []
for i in c:
p.append(''.join(i))
return p
This never calls the A choose n branch because len(A) is always
bigger than n.
Duh slaps forehead. It was supposed to be
if nlen(A):
That explains why it worked from the Idle prompt. I thought the
functions was executing c = probstat.Permutation(A,n), so that's
what I typed at the prompt.
print 'permutation w/o replacemment abcdefghijklmnopqrstuvwxyz:4'
t0 = time.time()
p = p_perm(abcdefghijklmnopqrstuvwxyz, 4)
t1 = time.time()
print len(p),'4-letter words',t1-t0,'seconds'
Unfortunately, the long test died (out of virtual memory) executing
the probstat.Permution test.
import probstat
p = probstat.Permutation(range(25))
len(p)
2076180480
p = probstat.Permutation(range(26))
len(p)
-1853882368
Overflow error. I'll have to add a test that raises a ValueError
for lists that are too big.
The following simple loop takes three minutes to run on my laptop
import probstat
count_to = len(probstat(range(12))) # just computes the size
cnt = 0
while cnt count_to:
cnt += 1
So a permutation of all arrangements of the alphabet would take
rougly forever.
Right, I never intended to do that, was trying to make 4-letter words,
not 26 letter permutations.
Anyway, now that _my_ bug is fixed, it works properly:
permutation w/ replacemment abcdefghijklmnopqrstuvwxyz:4
456976 4-letter words 1.2663242 seconds
combination w/ replacemment abcdefghijklmnopqrstuvwxyz:4
23751 4-letter words 0.67131335 seconds
permutation w/o replacemment abcdefghijklmnopqrstuvwxyz:4
358800 4-letter words 1.641049 seconds
combination w/o replacemment abcdefghijklmnopqrstuvwxyz:4
14950 4-letter words 0.5623624 seconds
probstat.Cartesian abcdefghijklmnopqrstuvwxyz:4
456976 4-letter words 1.4213134 seconds
probstat.Permutation abcdefghijklmnopqrstuvwxyz:4
358800 4-letter words 1.0623624 seconds
probstat.Combination abcdefghijklmnopqrstuvwxyz:4
14950 4-letter words 0.077999830246 seconds
Thanks again for supplying that pyd.
-Jack
--
http://mail.python.org/mailman/listinfo/python-list
Pulling all n-sized combinations from a list
Hi there, I've got a reasonably sized list of objects that I'd like to pull out all combinations of five elements from. Right now I have a way to do this that's quite slow, but manageable. I know there must be a better way to do this, but I'm not sure what it is. Here's what I've got so far: for a in myList: for b in myList: if a == b: break for c in myList: if b == c: break for d in myList: if c == d: break for e in myList: if d == e: break # my code here. Atrocious and slow, I'm sure, but is there a better way? I can't simply create a list with the combinations I want, since it won't fit into memory. And I'm sure I can do it using a standard paradigm using five indexed for loops (ie, for i = 1, for j = i+1, for k = j+1, etc.). But is there a really nice way to handle this in Python? Thanks for your time! Scott -- http://mail.python.org/mailman/listinfo/python-list
Re: Pulling all n-sized combinations from a list
Swroteb [EMAIL PROTECTED] writes: Atrocious and slow, I'm sure, but is there a better way? I can't simply create a list with the combinations I want, since it won't fit into memory. And I'm sure I can do it using a standard paradigm using five indexed for loops (ie, for i = 1, for j = i+1, for k = j+1, etc.). But is there a really nice way to handle this in Python? Is this a homework problem? Hint: 1) use recursion; 2) use generators. -- http://mail.python.org/mailman/listinfo/python-list
Re: Pulling all n-sized combinations from a list
Paul Rubin wrote: Swroteb [EMAIL PROTECTED] writes: Atrocious and slow, I'm sure, but is there a better way? I can't simply create a list with the combinations I want, since it won't fit into memory. And I'm sure I can do it using a standard paradigm using five indexed for loops (ie, for i = 1, for j = i+1, for k = j+1, etc.). But is there a really nice way to handle this in Python? Is this a homework problem? Hint: 1) use recursion; 2) use generators. I appreciate the response; no, this is not a homework problem. I'm a little bit confused about your generator suggestion. My list is a set of references to instantiated objects. I'm just unsure about how to iterate through every unique combination of those references. Are you suggesting that I set up methods to provide the indices I'm looking for in the list to iterate over? -- http://mail.python.org/mailman/listinfo/python-list
Re: Pulling all n-sized combinations from a list
Swroteb [EMAIL PROTECTED] writes: I'm a little bit confused about your generator suggestion. My list is a set of references to instantiated objects. I'm just unsure about how to iterate through every unique combination of those references. Are you suggesting that I set up methods to provide the indices I'm looking for in the list to iterate over? I think the natural approach is to make a generator that yields a 5-tuple for each combination, and then have your application iterate over that generator. Here's my version: def comb(x,n): Generate combinations of n items from list x if n==0: yield [] return for i in xrange(len(x)-n+1): for r in comb(x[i+1:], n-1): yield [x[i]] + r for c in comb([1,2,3,4,5], 3): print c The output is: [1, 2, 3] [1, 2, 4] [1, 2, 5] [1, 3, 4] [1, 3, 5] [1, 4, 5] [2, 3, 4] [2, 3, 5] [2, 4, 5] [3, 4, 5] -- http://mail.python.org/mailman/listinfo/python-list
Re: Pulling all n-sized combinations from a list
Paul Rubin wrote: I think the natural approach is to make a generator that yields a 5-tuple for each combination, and then have your application iterate over that generator. Here's my version: def comb(x,n): Generate combinations of n items from list x if n==0: yield [] return for i in xrange(len(x)-n+1): for r in comb(x[i+1:], n-1): yield [x[i]] + r for c in comb([1,2,3,4,5], 3): print c The output is: [1, 2, 3] [1, 2, 4] [1, 2, 5] [1, 3, 4] [1, 3, 5] [1, 4, 5] [2, 3, 4] [2, 3, 5] [2, 4, 5] [3, 4, 5] Ah, this definitely seems to work! It's a lot nicer in appearance than my previous code, that's for sure. It actually runs in approximately the same amount of time though. So, using your comb method, I have the following code now: myCombinations = comb(myList, 5) for a, b, c, d, e in myCombinations: # my code myList is 48 elements in size, so I'm going to get 1712304 combinations. From what I can tell, my speed problems aren't in the list generation anymore. Thanks for the assistance, Paul! I appreciate it. :) -- http://mail.python.org/mailman/listinfo/python-list
Re: Pulling all n-sized combinations from a list
Ah, this definitely seems to work! It's a lot nicer in appearance than my previous code, that's for sure. It actually runs in approximately the same amount of time though. As a side note, this problem will always be slow. The number of combinations grows exponentially with n. No matter how fast you generate a combination, generating them all it's going to take a lot of time if n is slighty bigger. -- http://mail.python.org/mailman/listinfo/python-list
Re: Pulling all n-sized combinations from a list
Swroteb wrote: Paul Rubin wrote: I think the natural approach is to make a generator that yields a 5-tuple for each combination, and then have your application iterate over that generator. Here's my version: def comb(x,n): Generate combinations of n items from list x if n==0: yield [] return for i in xrange(len(x)-n+1): for r in comb(x[i+1:], n-1): yield [x[i]] + r for c in comb([1,2,3,4,5], 3): print c The output is: [1, 2, 3] [1, 2, 4] [1, 2, 5] [1, 3, 4] [1, 3, 5] [1, 4, 5] [2, 3, 4] [2, 3, 5] [2, 4, 5] [3, 4, 5] Ah, this definitely seems to work! It's a lot nicer in appearance than my previous code, that's for sure. It actually runs in approximately the same amount of time though. So, using your comb method, I have the following code now: myCombinations = comb(myList, 5) for a, b, c, d, e in myCombinations: # my code myList is 48 elements in size, so I'm going to get 1712304 combinations. From what I can tell, my speed problems aren't in the list generation anymore. Thanks for the assistance, Paul! I appreciate it. :) If you're concerned about speed, and don't mind lack of flexibility, spelling out the iteration within your function is much faster: def comb(seq): indices = range(len(seq)) for ia in indices: a = seq[ia] for ib in indices[ia+1:]: b = seq[ib] for ic in indices[ib+1:]: c = seq[ic] for id in indices[ic+1:]: d = seq[id] for ie in indices[id+1:]: e = seq[ie] This is roughly 30 times faster on my box than the general solution above Michael -- http://mail.python.org/mailman/listinfo/python-list
Re: Pulling all n-sized combinations from a list
Michael Spencer [EMAIL PROTECTED] writes: This is roughly 30 times faster on my box than the general solution above Good point. You could probably improve the generator version some (probably not 30x) by doing less list arithmetic and slicing though. I just wrote it the most straightforward way I could. You could probably speed up the nested-loops version somewhat too, by keeping track of the indices instead of doing all that list slicing. -- http://mail.python.org/mailman/listinfo/python-list
Re: Pulling all n-sized combinations from a list
Yes, certainly. I hadn't done any profiling up to that point, but it really seemed like my biggest time sink was inefficiently losing time in obtaining the combinations. -- http://mail.python.org/mailman/listinfo/python-list
