Velocity Reviews > Combinations or Permutations

Combinations or Permutations

Seth Leija
Guest
Posts: n/a

 09-20-2010
I need to know how to generate a list of combinations/permutations
(can't remember which it is). Say I have a list of variables:

[a,b,c,d,...,x,y,z]

I am curious if there is an optimized way to generate this:

[[a,b],[a,c],[a,d],...,[x,z],[y,z]]

I currently have an iteration that does this:

#list.py

from math import *

list1=['a','b','c','d','e']
list2=[]
length=len(list1)

for it1 in range(0 ,length):
for it2 in range(it1+1, length):
list2.append([list1[it1],list1[it2]])

print list2

However, this is one of the slowest parts of my function (beaten only
by variable instantiation). I posted this on another forum looking to
see if there was a different method completely. They said that my
method was about as simple as it could get, but I might be able to
find out how to optimize my code here.

Mark Lawrence
Guest
Posts: n/a

 09-20-2010
On 20/09/2010 21:54, Seth Leija wrote:
> I need to know how to generate a list of combinations/permutations
> (can't remember which it is). Say I have a list of variables:
>
> [a,b,c,d,...,x,y,z]
>
> I am curious if there is an optimized way to generate this:
>
> [[a,b],[a,c],[a,d],...,[x,z],[y,z]]
>
> I currently have an iteration that does this:
>
> #list.py
>
> from math import *
>
> list1=['a','b','c','d','e']
> list2=[]
> length=len(list1)
>
> for it1 in range(0 ,length):
> for it2 in range(it1+1, length):
> list2.append([list1[it1],list1[it2]])
>
> print list2
>
> However, this is one of the slowest parts of my function (beaten only
> by variable instantiation). I posted this on another forum looking to
> see if there was a different method completely. They said that my
> method was about as simple as it could get, but I might be able to
> find out how to optimize my code here.
>
> Thanks in advance.

Check the docs for the itertools module.

Cheers.

Mark Lawrence.

Seth Leija
Guest
Posts: n/a

 09-20-2010
On Sep 20, 3:08*pm, Mark Lawrence <(E-Mail Removed)> wrote:
> On 20/09/2010 21:54, Seth Leija wrote:
>
>
>
>
>
> > I need to know how to generate a list of combinations/permutations
> > (can't remember which it is). Say I have a list of variables:

>
> > [a,b,c,d,...,x,y,z]

>
> > I am curious if there is an optimized way to generate this:

>
> > [[a,b],[a,c],[a,d],...,[x,z],[y,z]]

>
> > I currently have an iteration that does this:

>
> > #list.py

>
> > from math import *

>
> > list1=['a','b','c','d','e']
> > list2=[]
> > length=len(list1)

>
> > for it1 in range(0 ,length):
> > * * *for it2 in range(it1+1, length):
> > * * * * *list2.append([list1[it1],list1[it2]])

>
> > print list2

>
> > However, this is one of the slowest parts of my function (beaten only
> > by variable instantiation). I posted this on another forum looking to
> > see if there was a different method completely. They said that my
> > method was about as simple as it could get, but I might be able to
> > find out how to optimize my code here.

>
> > Thanks in advance.

>
> Check the docs for the itertools module.
>
> Cheers.
>
> Mark Lawrence.

That works! That made my function significantly faster! It's still
slower than I would like it, but this is enough for now. Thank you so
much!

Dave Angel
Guest
Posts: n/a

 09-20-2010
On 2:59 PM, Seth Leija wrote:
> I need to know how to generate a list of combinations/permutations
> (can't remember which it is). Say I have a list of variables:
>
> [a,b,c,d,...,x,y,z]
>
> I am curious if there is an optimized way to generate this:
>
> [[a,b],[a,c],[a,d],...,[x,z],[y,z]]
>
> I currently have an iteration that does this:
>
> #list.py
>
> from math import *
>
> list1=['a','b','c','d','e']
> list2=[]
> length=len(list1)
>
> for it1 in range(0 ,length):
> for it2 in range(it1+1, length):
> list2.append([list1[it1],list1[it2]])
>
> print list2
>
> However, this is one of the slowest parts of my function (beaten only
> by variable instantiation). I posted this on another forum looking to
> see if there was a different method completely. They said that my
> method was about as simple as it could get, but I might be able to
> find out how to optimize my code here.
>
> Thanks in advance.
>

You're apparently looking for combinations. You're asking for all the
combinations of items from the original list, taken two at a time.

Permutations would also include the reverse of each item, so it would be
exactly twice the size.

For the specific case of two, your approach is about as simple as it can
get. However, generalizing the code to handle 'r' at a time is pretty
tricky. There's a library function for it in Python 2.6 and later, as
mentioned by others, and the docs show a sample implementation.

Clearly making a single function call is optimized in one sense.
However, if you're looking for speed, chances are you could improve on
your own function by changing the two loops. (tested in python 2.6)

Consider:

list1=['a','b','c','d','e']
list2=[]

for it1, val1 in enumerate(list1):
for val2 in list1[it1+1:]:
list2.append([val1, val2])

print list2

DaveA

Raymond Hettinger
Guest
Posts: n/a

 09-21-2010
On Sep 20, 1:54*pm, Seth Leija <(E-Mail Removed)> wrote:
> I need to know how to generate a list of combinations/permutations
> (can't remember which it is). Say I have a list of variables:
>
> [a,b,c,d,...,x,y,z]
>
> I am curious if there is an optimized way to generate this:
>
> [[a,b],[a,c],[a,d],...,[x,z],[y,z]]

Try this:

>>> from itertools import combinations
>>> list(combinations('abcde', 2))

[('a', 'b'), ('a', 'c'), ('a', 'd'), ('a', 'e'), ('b', 'c'), ('b',
'd'), ('b', 'e'), ('c', 'd'), ('c', 'e'), ('d', 'e')]

Raymond

 Posting Rules You may not post new threads You may not post replies You may not post attachments You may not edit your posts BB code is On Smilies are On [IMG] code is On HTML code is OffTrackbacks are On Pingbacks are On Refbacks are Off Forum Rules

 Similar Threads Thread Thread Starter Forum Replies Last Post zgfareed@gmail.com C++ 6 09-26-2007 12:42 AM Peter Ensch Perl Misc 5 06-13-2006 09:45 PM Jeff Kish C++ 9 03-11-2005 06:10 AM Alex Vinokur C++ 2 05-13-2004 02:14 PM jose luis fernandez diaz C++ 6 04-13-2004 06:08 PM