Pulling all n-sized combinations from a list

[Swroteb]

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

[Paul Rubin]

"Swroteb" <sw*******@gmail.com> 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.

[Swroteb]

Paul Rubin wrote:

"Swroteb" <sw*******@gmail.com> 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?

[Paul Rubin]

"Swroteb" <sw*******@gmail.com> 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]

[Swroteb]

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. :)

[my.correo.basura]

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

[Michael Spencer]

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

[Paul Rubin]

Michael Spencer <ma**@telcopartners.com> 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.

[Swroteb]

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.

[Jack Diederich]

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

[mensanator]

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

[Fredrik Lundh]

me********@aol.com 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>

[Jack Diederich]

On Thu, Feb 09, 2006 at 10:23:12AM -0800, me********@aol.com 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

[mensanator]

Fredrik Lundh wrote:

me********@aol.com 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>

[Fredrik Lundh]

me********@aol.com wrote:

Fredrik Lundh wrote:

me********@aol.com 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>

[Magnus Lycka]

me********@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. 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.

[mensanator]

Magnus Lycka wrote:

me********@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.
He might be a little annoying at times, but he know what he's talking about.

[mensanator]

Jack Diederich wrote:

On Thu, Feb 09, 2006 at 10:23:12AM -0800, me********@aol.com 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 (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

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('abcdefghijklmnopqrstuvw xyz'),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]

liberally snipped out parts
On Thu, Feb 09, 2006 at 03:25:18PM -0800, me********@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
>
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

[mensanator]

Jack Diederich wrote:

liberally snipped out parts
On Thu, Feb 09, 2006 at 03:25:18PM -0800, me********@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
> >
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 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]

me********@aol.com wrote:

But using the free SDK compiler from MS? That seems elusive.

Have you seen this?
http://www.vrplumber.com/programming/mstoolkit/

[mensanator]

Magnus Lycka wrote:

me********@aol.com 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.

[Magnus Lycka]

me********@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?

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

[mensanator]

Magnus Lycka wrote:

me********@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?

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?

[Steve Holden]

me********@aol.com wrote:

Magnus Lycka wrote:

me********@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 [phone] [phone]
Holden Web LLC www.holdenweb.com
PyCon TX 2006 www.python.org/pycon/

[jess.austin]

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 (a>b and b>c and c>d)])
14950

cheers,
Jess

[mensanator]

je*********@gmail.com 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 (a>b and b>c and c>d)])
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 (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