Combinations or Permutations

Discussion in 'Python' started by Seth Leija, Sep 20, 2010.

  1. Seth Leija

    Seth Leija Guest

    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.
    Seth Leija, Sep 20, 2010
    #1
    1. Advertising

  2. 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.
    Mark Lawrence, Sep 20, 2010
    #2
    1. Advertising

  3. Seth Leija

    Seth Leija Guest

    On Sep 20, 3:08 pm, Mark Lawrence <> 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!
    Seth Leija, Sep 20, 2010
    #3
  4. Seth Leija

    Dave Angel Guest

    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
    Dave Angel, Sep 21, 2010
    #4
  5. On Sep 20, 1:54 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]]


    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
    Raymond Hettinger, Sep 21, 2010
    #5
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. jose luis fernandez diaz

    Combinations/permutations algorithm in C++

    jose luis fernandez diaz, Apr 13, 2004, in forum: C++
    Replies:
    6
    Views:
    14,089
    Leor Zolman
    Apr 13, 2004
  2. Alex Vinokur
    Replies:
    2
    Views:
    2,772
    Alex Vinokur
    May 13, 2004
  3. Jeff Kish

    permutations and combinations

    Jeff Kish, Mar 7, 2005, in forum: C++
    Replies:
    9
    Views:
    2,258
    DHOLLINGSWORTH2
    Mar 11, 2005
  4. Replies:
    6
    Views:
    430
  5. Peter Ensch
    Replies:
    5
    Views:
    190
Loading...

Share This Page