Pulling all n-sized combinations from a list
Swroteb
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
Paul Rubin
> 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.
Swroteb
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?
Paul Rubin
> 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]
>>>
Swroteb
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. :)
my.corre...@gmail.com
> 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.
Michael Spencer
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
Paul Rubin
> 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.
Swroteb
really seemed like my biggest time sink was inefficiently losing time
in obtaining the combinations.
Jack Diederich
> 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
mensa...@aol.com
Did you ever figure that some people use Windows?
>
> -jackdied
Fredrik Lundh
> > 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>
Jack Diederich
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
mensa...@aol.com
Windows comes with a C compiler? That's news to me.
>
> </F>
Fredrik Lundh
Magnus Lycka
>
>
> 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.
mensa...@aol.com
Magnus Lycka wrote:
> mensa...@aol.com 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.
mensa...@aol.com
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 (n>len(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%s>i%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 = ooloop5("abcdefghijklmnopqrstuvwxyz", 4, False, False)
t1 = time.time()
print len(p),'4-letter words',t1-t0,'seconds'
print 'probstat.Cartesian "abcdefghijklmnopqrstuvwxyz":4'
t0 = time.time()
p = p_cart('abcdefghijklmnopqrstuvwxyz',4)
t1 = time.time()
print len(p),'4-letter words',t1-t0,'seconds'
print 'probstat.Permutation "abcdefghijklmnopqrstuvwxyz":4'
t0 = time.time()
p = p_perm('abcdefghijklmnopqrstuvwxyz',4)
t1 = time.time()
print len(p),'4-letter words',t1-t0,'seconds'
print 'probstat.Combination "abcdefghijklmnopqrstuvwxyz":4'
t0 = time.time()
p = p_comb('abcdefghijklmnopqrstuvwxyz',4)
t1 = time.time()
print len(p),'4-letter words',t1-t0,'seconds'
-----------------------------------------------------
The short tests worked out fine
permutation w/ replacemment
['aaa', 'aab', 'aac', 'aba', 'abb', 'abc', 'aca', 'acb', 'acc', 'baa',
'bab', 'bac', 'bba', 'bbb', 'bbc', 'bca', 'bcb', 'bcc', 'caa', 'cab',
'cac', 'cba', 'cbb', 'cbc', 'cca', 'ccb', 'ccc']
combination w/ replacemment
['aaa', 'aab', 'aac', 'abb', 'abc', 'acc', 'bbb', 'bbc', 'bcc', 'ccc']
permutation w/o replacemment
['abc', 'acb', 'bac', 'bca', 'cab', 'cba']
combination w/o replacemment
['abc']
probstat.Cartesian
['aaa', 'baa', 'caa', 'aba', 'bba', 'cba', 'aca', 'bca', 'cca', 'aab',
'bab', 'cab', 'abb', 'bbb', 'cbb', 'acb', 'bcb', 'ccb', 'aac', 'bac',
'cac', 'abc', 'bbc', 'cbc', 'acc', 'bcc', 'ccc']
probstat.Permutation
['abc', 'acb', 'bac', 'bca', 'cab', 'cba']
probstat.Combination
['abc']
-----------------------------------------------------
Unfortunately, the long test died (out of virtual memory) executing
the probstat.Permution test.
But here's the strange thing. When executed from the Idle prompt,
it works fine.
>>> import probstat
>>> A = list('abcdefghijklmnopqrstuvwxyz')
>>> c = probstat.Permutation(A,4)
>>> print len(c)
358800
>>> for i in c[:10]:print i
['a', 'b', 'c', 'd']
['a', 'b', 'd', 'c']
['a', 'c', 'b', 'd']
['a', 'c', 'd', 'b']
['a', 'd', 'b', 'c']
['a', 'd', 'c', 'b']
['b', 'a', 'c', 'd']
['b', 'a', 'd', 'c']
['b', 'c', 'a', 'd']
['b', 'c', 'd', 'a']
>>> p = []
>>> for i in c: p.append(''.join(i))
>>>
>>> for i in p[:10]:print i
abcd
abdc
acbd
acdb
adbc
adcb
bacd
badc
bcad
bcda
-----------------------------------------------------
And if I comment out the Permutation test, everything else
works ok.
permutation w/ replacemment "abcdefghijklmnopqrstuvwxyz":4
456976 4-letter words 1.23500013351 seconds
combination w/ replacemment "abcdefghijklmnopqrstuvwxyz":4
23751 4-letter words 0.68799996376 seconds
permutation w/o replacemment "abcdefghijklmnopqrstuvwxyz":4
358800 4-letter words 1.67199993134 seconds
combination w/o replacemment "abcdefghijklmnopqrstuvwxyz":4
14950 4-letter words 0.59299993515 seconds
probstat.Cartesian "abcdefghijklmnopqrstuvwxyz":4
456976 4-letter words 1.42200016975 seconds
probstat.Combination "abcdefghijklmnopqrstuvwxyz":4
14950 4-letter words 0.0780000686646 seconds
-----------------------------------------------------
But it fails if I call it from inside a function.
>>> import probstat
>>> import time
>>> def p_perm(a,n):
A = list(a)
if len(A)<n:
c = probstat.Permutation(A,n)
else:
c = probstat.Permutation(A)
p = []
for i in c:
p.append(''.join(i))
return p
>>> p = p_perm('abcdefghijklmnopqrstuvwxyz',4)
Crash! Out of virtual memory.
-----------------------------------------------------
I noticed that the probstat call takes virtually no time, most of it
taken by the p.append loop.
>>> def p_perm(a,n):
A = list(a)
if len(A)<n:
c = probstat.Permutation(A,n)
else:
c = probstat.Permutation(A)
print 'probstat finished'
p = []
for i in c:
p.append(''.join(i))
return p
>>> p = p_perm('abcdefghijklmnopqrstuvwxyz',4)
probstat finished
Aha! Must be dying during the p.append loop.
-----------------------------------------------------
So we'll skip the append for now.
def p_perm(a,n):
A = list(a)
t0 = time.time()
if len(A)<n:
q = probstat.Permutation(A,n)
else:
q = probstat.Permutation(A)
print time.time()-t0
#p = []
#for i in c:
# p.append(''.join(i))
#return p
print len(q)
for i in q[:10]: print i
return q
probstat.Permutation "abcdefghijklmnopqrstuvwxyz":4
0.0
-1853882368
['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n',
'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z']
['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n',
'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'z', 'y']
['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n',
'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'y', 'x', 'z']
['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n',
'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'y', 'z', 'x']
['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n',
'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'z', 'x', 'y']
['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n',
'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'z', 'y', 'x']
['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n',
'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'x', 'w', 'y', 'z']
['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n',
'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'x', 'w', 'z', 'y']
['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n',
'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'x', 'y', 'w', 'z']
['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n',
'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'x', 'y', 'z', 'w']
-1853882368 4-letter words 0.25 seconds
HUH??? No wonder the append loop has convulsions!
and why are the lists length 26? s/b len 4.
And yet...
>>> q = probstat.Permutation(list('abcdefghijklmnopqrstuvwxyz'),4)
>>> print len(q)
358800
>>> for i in q[:10]:print i
['a', 'b', 'c', 'd']
['a', 'b', 'd', 'c']
['a', 'c', 'b', 'd']
['a', 'c', 'd', 'b']
['a', 'd', 'b', 'c']
['a', 'd', 'c', 'b']
['b', 'a', 'c', 'd']
['b', 'a', 'd', 'c']
['b', 'c', 'a', 'd']
['b', 'c', 'd', 'a']
-----------------------------------------------------
That's one of the strangest problems I've ever seen.
I don't know if this has anything to do with the pyd file,
but I figured you would like to know.
Jack Diederich
On Thu, Feb 09, 2006 at 03:25:18PM -0800, mensa...@aol.com 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
> > > >
>
> compares. Correspondence to my emulations is (as far as I can tell)
>
>
> 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
mensa...@aol.com
Duh <slaps forehead>. It was supposed to be
if n<len(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.26600003242 seconds
combination w/ replacemment "abcdefghijklmnopqrstuvwxyz":4
23751 4-letter words 0.671999931335 seconds
permutation w/o replacemment "abcdefghijklmnopqrstuvwxyz":4
358800 4-letter words 1.6400001049 seconds
combination w/o replacemment "abcdefghijklmnopqrstuvwxyz":4
14950 4-letter words 0.56200003624 seconds
probstat.Cartesian "abcdefghijklmnopqrstuvwxyz":4
456976 4-letter words 1.42199993134 seconds
probstat.Permutation "abcdefghijklmnopqrstuvwxyz":4
358800 4-letter words 1.06200003624 seconds
probstat.Combination "abcdefghijklmnopqrstuvwxyz":4
14950 4-letter words 0.077999830246 seconds
Thanks again for supplying that pyd.
>
> -Jack
Magnus Lycka
> But using the free SDK compiler from MS? That seems elusive.
Have you seen this?
http://www.vrplumber.com/programming/mstoolkit/
mensa...@aol.com
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.
Magnus Lycka
> 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
mensa...@aol.com
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?
Steve Holden
> Magnus Lycka wrote:
>
>>mensa...@aol.com 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/
jess....@gmail.com
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 (a>b and b>c and c>d)])
14950
cheers,
Jess
mensa...@aol.com
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 (n>len(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%s>c%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