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

-- 
http://mail.python.org/mailman/listinfo/python-list

Re: Pulling all n-sized combinations from a list

[Swroteb]

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]

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

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

-- 
http://mail.python.org/mailman/listinfo/python-list