How to get all possible combinations of a list s elements

Question

I have a list with 15 numbers in  and I need to write some code that produces all 32 768 combinations of those numbers    I ve found some code  by Googling  that apparently does what I m looking for  but I found the code fairly opaque and am wary of using it  Plus I have a feeling there must be a more elegant solution   The only thing that occurs to me would be to just loop through the decimal integers 1   32768 and convert those to binary  and use the binary representation as a filter to pick out the appropriate numbers    Does anyone know of a better way  Using map    maybe

User · Answer

3 functions   all combinations of n elements list all combinations of n elements list where order is not distinct all permutations  import sys  def permutations a       return combinations a  len a    def combinations a  n       if n    1          for x in a              yield  x      else          for i in range len a                for x in combinations a  i    a i 1    n-1                   yield  a i     x  def combinationsNoOrder a  n       if n    1          for x in a              yield  x      else          for i in range len a                for x in combinationsNoOrder a  i   n-1                   yield  a i     x      if   name       quot   main   quot       for s in combinations list map int  sys argv 2      int sys argv 1             print s

User · Answer

from itertools import permutations  combinations   features     A    B    C   tmp      for i in range len features        oc   combinations features  i   1      for c in oc          tmp append list c       output       A       B       C       A    B       A    C       B    C       A    B    C

User · Answer

This is my implementation def get combinations list of things    quot  quot  quot gets every combination of things in a list returned as a list of lists  Should be read   add all combinations of a certain size to the end of a list for every possible size in the the list of things    quot  quot  quot  list of combinations    list combinations of a certain size                          for possible size of combinations in range 1   len list of things                           for combinations of a certain size in itertools combinations list of things                                                                                       possible size of combinations   return list of combinations

User · Answer

I thought I would add this function for those seeking an answer without importing itertools or any other extra libraries   def powerSet items               Power set generator  get all possible combinations of a list   s elements      Input          items is a list     Output          returns 2  n combination lists one at a time using a generator       Reference  edx org 6 00 2x Lecture 2 - Decision Trees and dynamic programming              N   len items        enumerate the 2  N possible combinations     for i in range 2  N           combo              for j in range N                 test bit jth of integer i             if  i  gt  gt  j    2    1                  combo append items j           yield combo   Simple Yield Generator Usage   for i in powerSet  1 2 3 4        print  i         end       Output from Usage example above             1     2     1  2     3     1  3     2  3     1  2  3     4       1  4      2  4     1  2  4     3  4     1  3  4     2  3  4     1  2    3  4

User · Answer

Here s a lazy one-liner  also using itertools   from itertools import compress  product  def combinations items       return   set compress items mask   for mask in product    0 1   len items           alternative                          in product  0 1   repeat len items       Main idea behind this answer  there are 2 N combinations -- same as the number of binary strings of length N  For each binary string  you pick all elements corresponding to a  1    items abc   mask         V 000 - gt   001 - gt    c 010 - gt   b 011 - gt   bc 100 - gt  a 101 - gt  a c 110 - gt  ab 111 - gt  abc   Things to consider    This requires that you can call len      on items  workaround  if items is something like an iterable like a generator  turn it into a list first with items list  itemsArg   This requires that the order of iteration on items is not random  workaround  don t be insane  This requires that the items are unique  or else  2 2 1  and  2 1 1  will both collapse to  2 1   workaround  use collections Counter as a drop-in replacement for set  it s basically a multiset    though you may need to later use tuple sorted Counter      elements     if you need it to be hashable      Demo   gt  gt  gt  list combinations range 4     set     3    2    2  3    1    1  3    1  2    1  2  3    0    0  3    0  2    0  2  3    0  1    0  1  3    0  1  2    0  1  2  3     gt  gt  gt  list combinations  abcd     set      d      c      c    d      b      b    d      c    b      c    b    d      a      a    d      a    c      a    c    d      a    b      a    b    d      a    c    b      a    c    b    d

User · Answer

This answer missed one aspect  the OP asked for ALL combinations    not just combinations of length  r    So you d either have to loop through all lengths  L    import itertools  stuff    1  2  3  for L in range 0  len stuff  1       for subset in itertools combinations stuff  L           print subset    Or -- if you want to get snazzy  or bend the brain of whoever reads your code after you  -- you can generate the chain of  combinations    generators  and iterate through that   from itertools import chain  combinations def all subsets ss       return chain  map lambda x  combinations ss  x   range 0  len ss  1     for subset in all subsets stuff       print subset

User · Answer

flag   0 requiredCals  12 from itertools import chain  combinations  def powerset iterable       s   list iterable     allows duplicate elements     return chain from iterable combinations s  r  for r in range len s  1    stuff    2 9 5 1 6  for i  combo in enumerate powerset stuff   1       if len combo  gt 0            print combo   sum combo           if sum combo    requiredCals               flag   1             break if flag  1       print  True   else      print  else

User · Answer

Using list comprehension   def selfCombine  list2Combine  length        listCombined   str    list2Combine i    str  i         for i in range  length      replace                                      for i0 in range len  list2Combine          if length  gt  1          listCombined    str     for i    str  i       in range  i    str  i - 1        len  list2Combine      for i in range  1  length                    replace                              replace                           replace                  listCombined         listCombined           listCombined   eval  listCombined        return listCombined  list2Combine     A    B    C   listCombined   selfCombine  list2Combine  2     Output would be     A    A     A    B     A    C     B    B     B    C     C    C

User · Answer

How about this   used a string instead of list  but same thing   string can be treated like a list in Python   def comb s  res       if not s  return     res add s      for i in range 0  len s            t   s 0 i    s i   1           comb t  res   res   set   comb  game   res    print res

User · Answer

If someone is looking for a reversed list  like I was   stuff    1  2  3  4   def reverse bla  y       for subset in itertools combinations bla  len bla -y           print list subset      if y    len bla           y    1         reverse bla  y   reverse stuff  1

User · Answer

I know it s far more practical to use itertools to get the all the combinations  but you can achieve this partly with only list comprehension if you so happen to desire  granted you want to code a lot For combinations of two pairs  lambda l    a  b  for i  a in enumerate l  for b in l i 1     And  for combinations of three pairs  it s as easy as this  lambda l    a  b  c  for i  a in enumerate l  for ii  b in enumerate l i 1    for c in l i ii 2      The result is identical to using itertools combinations  import itertools combs 3   lambda l         a  b  c  for i  a in enumerate l       for ii  b in enumerate l i 1         for c in l i ii 2     data     1  2   5   quot a quot   None  print  quot A  quot   list itertools combinations data  3    print  quot B  quot   combs 3 data     A     1  2   5   a      1  2   5  None     1  2    a   None    5   a   None     B     1  2   5   a      1  2   5  None     1  2    a   None    5   a   None

User · Answer

Here is one using recursion    gt  gt  gt  import copy  gt  gt  gt  def combinations target data           for i in range len data                new target   copy copy target              new data   copy copy data              new target append data i               new data   data i 1               print new target             combinations new target                           new data                                  gt  gt  gt  target       gt  gt  gt  data     a   b   c   d    gt  gt  gt    gt  gt  gt  combinations target data    a     a    b     a    b    c     a    b    c    d     a    b    d     a    c     a    c    d     a    d     b     b    c     b    c    d     b    d     c     c    d     d

User · Answer

Have a look at itertools combinations    itertools combinations iterable  r        Return r length subsequences of elements from   the input iterable       Combinations are emitted in lexicographic sort order  So  if the   input iterable is sorted  the   combination tuples will be produced in   sorted order    Since 2 6  batteries are included

User · Answer

This answer missed one aspect  the OP asked for ALL combinations    not just combinations of length  r    So you d either have to loop through all lengths  L    import itertools  stuff    1  2  3  for L in range 0  len stuff  1       for subset in itertools combinations stuff  L           print subset    Or -- if you want to get snazzy  or bend the brain of whoever reads your code after you  -- you can generate the chain of  combinations    generators  and iterate through that   from itertools import chain  combinations def all subsets ss       return chain  map lambda x  combinations ss  x   range 0  len ss  1     for subset in all subsets stuff       print subset

User · Answer

I thought I would add this function for those seeking an answer without importing itertools or any other extra libraries   def powerSet items               Power set generator  get all possible combinations of a list   s elements      Input          items is a list     Output          returns 2  n combination lists one at a time using a generator       Reference  edx org 6 00 2x Lecture 2 - Decision Trees and dynamic programming              N   len items        enumerate the 2  N possible combinations     for i in range 2  N           combo              for j in range N                 test bit jth of integer i             if  i  gt  gt  j    2    1                  combo append items j           yield combo   Simple Yield Generator Usage   for i in powerSet  1 2 3 4        print  i         end       Output from Usage example above             1     2     1  2     3     1  3     2  3     1  2  3     4       1  4      2  4     1  2  4     3  4     1  3  4     2  3  4     1  2    3  4

User · Answer

I m late to the party but would like to share the solution I found to the same issue  Specifically  I was looking to do sequential combinations  so for  quot STAR quot  I wanted  quot STAR quot    quot TA quot    quot AR quot   but not  quot SR quot   lst    S  T  A  R  lstCombos      for Length in range 0 len lst  1       for i in lst          lstCombos append lst lst index i  lst index i  Length    Duplicates can be filtered with adding in an additional if before the last line  lst    S  T  A  R  lstCombos      for Length in range 0 len lst  1       for i in lst           if not lst lst index i  lst index i  Length   in lstCombos               lstCombos append lst lst index i  lst index i  Length    If for some reason this returns blank lists in the output  which happened to me  I added  for subList in lstCombos      if subList                lstCombos remove subList

User · Answer

Without using itertools   def combine inp       return combine helper inp            def combine helper inp  temp  ans       for i in range len inp            current   inp i          remaining   inp i   1           temp append current          ans append tuple temp           combine helper remaining  temp  ans          temp pop       return ans   print combine   a    b    c    d

User · Answer

from itertools import permutations  combinations   features     A    B    C   tmp      for i in range len features        oc   combinations features  i   1      for c in oc          tmp append list c       output       A       B       C       A    B       A    C       B    C       A    B    C

User · Answer

I know it s far more practical to use itertools to get the all the combinations  but you can achieve this partly with only list comprehension if you so happen to desire  granted you want to code a lot For combinations of two pairs  lambda l    a  b  for i  a in enumerate l  for b in l i 1     And  for combinations of three pairs  it s as easy as this  lambda l    a  b  c  for i  a in enumerate l  for ii  b in enumerate l i 1    for c in l i ii 2      The result is identical to using itertools combinations  import itertools combs 3   lambda l         a  b  c  for i  a in enumerate l       for ii  b in enumerate l i 1         for c in l i ii 2     data     1  2   5   quot a quot   None  print  quot A  quot   list itertools combinations data  3    print  quot B  quot   combs 3 data     A     1  2   5   a      1  2   5  None     1  2    a   None    5   a   None     B     1  2   5   a      1  2   5  None     1  2    a   None    5   a   None

User · Answer

This is an approach that can be easily transfered to all programming languages supporting recursion  no itertools  no yield  no list comprehension    def combs a       if len a     0          return          cs          for c in combs a 1             cs     c  c  a 0        return cs   gt  gt  gt  combs  1 2 3 4 5         1    2    2  1    3    3  1    3  2         5  4  3  2  1

User · Answer

Have a look at itertools combinations    itertools combinations iterable  r        Return r length subsequences of elements from   the input iterable       Combinations are emitted in lexicographic sort order  So  if the   input iterable is sorted  the   combination tuples will be produced in   sorted order    Since 2 6  batteries are included

User · Answer

I agree with Dan H that Ben indeed asked for all combinations  itertools combinations   does not give all combinations   Another issue is  if the input iterable is big  it is perhaps better to return a generator instead of everything in a list   iterable   range 10  for s in xrange len iterable  1     for comb in itertools combinations iterable  s       yield comb

User · Answer

Without itertools in Python 3 you could do something like this   def combinations arr  carry       for i in range len arr            yield carry   arr i          yield from combinations arr i   1    carry   arr i     where initially carry

User · Answer

This is my implementation def get combinations list of things    quot  quot  quot gets every combination of things in a list returned as a list of lists  Should be read   add all combinations of a certain size to the end of a list for every possible size in the the list of things    quot  quot  quot  list of combinations    list combinations of a certain size                          for possible size of combinations in range 1   len list of things                           for combinations of a certain size in itertools combinations list of things                                                                                       possible size of combinations   return list of combinations

User · Answer

Below is a  standard recursive answer   similar to the other similar answer https   stackoverflow com a 23743696 711085    We don t realistically have to worry about running out of stack space since there s no way we could process all N  permutations    It visits every element in turn  and either takes it or leaves it  we can directly see the 2 N cardinality from this algorithm    def combs xs  i 0       if i  len xs           yield            return     for c in combs xs i 1           yield c         yield c  xs i        Demo    gt  gt  gt  list  combs range 5           0     1     1  0    2     2  0    2  1    2  1  0    3     3  0    3  1    3  1  0    3  2    3  2  0    3  2  1    3  2  1  0    4     4  0    4  1    4  1  0    4  2    4  2  0    4  2  1    4  2  1  0    4  3    4  3  0    4  3  1    4  3  1  0    4  3  2    4  3  2  0    4  3  2  1    4  3  2  1  0     gt  gt  gt  list sorted  combs range 5    key len           0     1     2     3     4       1  0    2  0    2  1    3  0    3  1    3  2    4  0    4  1    4  2    4  3      2  1  0    3  1  0    3  2  0    3  2  1    4  1  0    4  2  0    4  2  1    4  3  0    4  3  1    4  3  2      3  2  1  0    4  2  1  0    4  3  1  0    4  3  2  0    4  3  2  1      4  3  2  1  0     gt  gt  gt  len set combs range 5     32

User · Answer

Below is a  standard recursive answer   similar to the other similar answer https   stackoverflow com a 23743696 711085    We don t realistically have to worry about running out of stack space since there s no way we could process all N  permutations    It visits every element in turn  and either takes it or leaves it  we can directly see the 2 N cardinality from this algorithm    def combs xs  i 0       if i  len xs           yield            return     for c in combs xs i 1           yield c         yield c  xs i        Demo    gt  gt  gt  list  combs range 5           0     1     1  0    2     2  0    2  1    2  1  0    3     3  0    3  1    3  1  0    3  2    3  2  0    3  2  1    3  2  1  0    4     4  0    4  1    4  1  0    4  2    4  2  0    4  2  1    4  2  1  0    4  3    4  3  0    4  3  1    4  3  1  0    4  3  2    4  3  2  0    4  3  2  1    4  3  2  1  0     gt  gt  gt  list sorted  combs range 5    key len           0     1     2     3     4       1  0    2  0    2  1    3  0    3  1    3  2    4  0    4  1    4  2    4  3      2  1  0    3  1  0    3  2  0    3  2  1    4  1  0    4  2  0    4  2  1    4  3  0    4  3  1    4  3  2      3  2  1  0    4  2  1  0    4  3  1  0    4  3  2  0    4  3  2  1      4  3  2  1  0     gt  gt  gt  len set combs range 5     32

User · Answer

flag   0 requiredCals  12 from itertools import chain  combinations  def powerset iterable       s   list iterable     allows duplicate elements     return chain from iterable combinations s  r  for r in range len s  1    stuff    2 9 5 1 6  for i  combo in enumerate powerset stuff   1       if len combo  gt 0            print combo   sum combo           if sum combo    requiredCals               flag   1             break if flag  1       print  True   else      print  else

User · Answer

Combination from itertools import itertools col names     quot aa quot   quot bb quot    quot cc quot    quot dd quot   all combinations   itertools chain   itertools combinations col names i 1  for i   in enumerate col names    print list all combinations

User · Answer

Without using itertools   def combine inp       return combine helper inp            def combine helper inp  temp  ans       for i in range len inp            current   inp i          remaining   inp i   1           temp append current          ans append tuple temp           combine helper remaining  temp  ans          temp pop       return ans   print combine   a    b    c    d

User · Answer

Combination from itertools import itertools col names     quot aa quot   quot bb quot    quot cc quot    quot dd quot   all combinations   itertools chain   itertools combinations col names i 1  for i   in enumerate col names    print list all combinations

User · Answer

You can generate all combinations of a list in Python using this simple code  import itertools  a    1 2 3 4  for i in xrange 0 len a  1      print list itertools combinations a i    Result would be         1     2     3     4      1  2    1  3    1  4    2  3    2  4    3  4     1  2  3    1  2  4    1  3  4    2  3  4     1  2  3  4

User · Answer

Have a look at itertools combinations    itertools combinations iterable  r        Return r length subsequences of elements from   the input iterable       Combinations are emitted in lexicographic sort order  So  if the   input iterable is sorted  the   combination tuples will be produced in   sorted order    Since 2 6  batteries are included

User · Answer

Using list comprehension   def selfCombine  list2Combine  length        listCombined   str    list2Combine i    str  i         for i in range  length      replace                                      for i0 in range len  list2Combine          if length  gt  1          listCombined    str     for i    str  i       in range  i    str  i - 1        len  list2Combine      for i in range  1  length                    replace                              replace                           replace                  listCombined         listCombined           listCombined   eval  listCombined        return listCombined  list2Combine     A    B    C   listCombined   selfCombine  list2Combine  2     Output would be     A    A     A    B     A    C     B    B     B    C     C    C

User · Answer

You can also use the powerset function from the excellent more itertools package   from more itertools import powerset  l    1 2 3  list powerset l            1     2     3     1  2    1  3    2  3    1  2  3     We can also verify  that it meets OP s requirement  from more itertools import ilen  assert ilen powerset range 15       32 768

User · Answer

Without itertools in Python 3 you could do something like this   def combinations arr  carry       for i in range len arr            yield carry   arr i          yield from combinations arr i   1    carry   arr i     where initially carry

User · Answer

Here is one using recursion    gt  gt  gt  import copy  gt  gt  gt  def combinations target data           for i in range len data                new target   copy copy target              new data   copy copy data              new target append data i               new data   data i 1               print new target             combinations new target                           new data                                  gt  gt  gt  target       gt  gt  gt  data     a   b   c   d    gt  gt  gt    gt  gt  gt  combinations target data    a     a    b     a    b    c     a    b    c    d     a    b    d     a    c     a    c    d     a    d     b     b    c     b    c    d     b    d     c     c    d     d

User · Answer

In comments under the highly upvoted answer by  Dan H  mention is made of the powerset   recipe in the itertools documentation   including one by Dan himself  However  so far no one has posted it as an answer  Since it s probably one of the better if not the best approach to the problem   and given a little encouragement from another commenter  it s shown below  The function produces all unique combinations of the list elements of every length possible  including those containing zero and all the elements    Note  If the  subtly different  goal is to obtain only combinations of unique elements  change the line s   list iterable  to s   list set iterable   to eliminate any duplicate elements  Regardless  the fact that the iterable is ultimately turned into a list means it will work with generators  unlike several of the other answers    from itertools import chain  combinations  def powerset iterable        powerset  1 2 3   -- gt      1    2    3    1 2   1 3   2 3   1 2 3       s   list iterable     allows duplicate elements     return chain from iterable combinations s  r  for r in range len s  1    stuff    1  2  3  for i  combo in enumerate powerset stuff   1       print  combo          format i  combo     Output   combo  1     combo  2   1   combo  3   2   combo  4   3   combo  5   1  2  combo  6   1  3  combo  7   2  3  combo  8   1  2  3

User · Answer

How about this   used a string instead of list  but same thing   string can be treated like a list in Python   def comb s  res       if not s  return     res add s      for i in range 0  len s            t   s 0 i    s i   1           comb t  res   res   set   comb  game   res    print res

User · Answer

Here are two implementations of itertools combinations  One that returns a list  def combinations lst  depth  start 0  items          if depth  lt   0          return  items      out          for i in range start  len lst            out    combinations lst  depth - 1  i   1  items    lst i        return out   One returns a generator  def combinations lst  depth  start 0  prepend          if depth  lt   0          yield prepend     else          for i in range start  len lst                for c in combinations lst  depth - 1  i   1  prepend    lst i                     yield c   Please note that providing a helper function to those is advised because the prepend argument is static and is not changing with every call  print  c for c in combinations  1  2  3  4   3        1  2  3    1  2  4    1  3  4    2  3  4      get a hold of prepend prepend    c for c in combinations     -1   0  prepend append None   print  c for c in combinations  1  2  3  4   3        None  1  2  3    None  1  2  4    None  1  3  4    None  2  3  4     This is a very superficial case but better be safe than sorry

User · Answer

3 functions   all combinations of n elements list all combinations of n elements list where order is not distinct all permutations  import sys  def permutations a       return combinations a  len a    def combinations a  n       if n    1          for x in a              yield  x      else          for i in range len a                for x in combinations a  i    a i 1    n-1                   yield  a i     x  def combinationsNoOrder a  n       if n    1          for x in a              yield  x      else          for i in range len a                for x in combinationsNoOrder a  i   n-1                   yield  a i     x      if   name       quot   main   quot       for s in combinations list map int  sys argv 2      int sys argv 1             print s

User · Answer

I agree with Dan H that Ben indeed asked for all combinations  itertools combinations   does not give all combinations   Another issue is  if the input iterable is big  it is perhaps better to return a generator instead of everything in a list   iterable   range 10  for s in xrange len iterable  1     for comb in itertools combinations iterable  s       yield comb

User · Answer

This one-liner gives you all the combinations  between 0 and n items if the original list set contains n distinct elements  and uses the native method itertools combinations   Python 2  from itertools import combinations  input     a    b    c    d    output   sum  map list  combinations input  i   for i in range len input    1          Python 3  from itertools import combinations  input     a    b    c    d    output   sum  list map list  combinations input  i    for i in range len input    1            The output will be           a       b       c       d       a    b       a    c       a    d       b    c       b    d       c    d       a    b    c       a    b    d       a    c    d       b    c    d       a    b    c    d        Try it online   http   ideone com COghfX

User · Answer

This code employs a simple algorithm with nested lists       FUNCTION getCombos  To generate all combos of an input list  consider the following sets of nested lists                                                      A                               A   B                A B                               A   B   C            A B   A C   B C                          A B C                               A   B   C   D        A B   A C   B C   A D   B D   C D        A B C   A B D   A C D   B C D        A B C D           There is a set of lists for each number of items that will occur in a combo  including an empty set      For each additional item  begin at the back of the list by adding an empty list  then taking the set of    lists in the previous column  e g   in the last list  for sets of 3 items you take the existing set of    3-item lists and append to it additional lists created by appending the item  4  to the lists in the    next smallest item count set  In this case  for the three sets of 2-items in the previous list  Repeat    for each set of lists back to the initial list containing just the empty list     def getCombos listIn     A   B   C   D   E   F          listCombos                    list of lists of combos  seeded with a list containing only the empty list     listSimple                    list to contain the final returned list of items  e g   characters       for item in listIn          listCombos append         append an emtpy list to the end for each new item added         for index in xrange len listCombos -1  0  -1      set the index range to work through the list             for listPrev in listCombos index-1            retrieve the lists from the previous column                 listCur   listPrev                        create a new temporary list object to update                 listCur append item                       add the item to the previous list to make it current                 listCombos index  append listCur          list length and append it to the current list                  itemCombo                                 Create a str to concatenate list items into a str                 for item in listCur                       concatenate the members of the lists to create                     itemCombo    item                     create a string of items                 listSimple append itemCombo               add to the final output list      return  listSimple  listCombos    END getCombos

User · Answer

You can generate all combinations of a list in Python using this simple code  import itertools  a    1 2 3 4  for i in xrange 0 len a  1      print list itertools combinations a i    Result would be         1     2     3     4      1  2    1  3    1  4    2  3    2  4    3  4     1  2  3    1  2  4    1  3  4    2  3  4     1  2  3  4

User · Answer

Here is yet another solution  one-liner   involving using the itertools combinations function  but here we use a double list comprehension  as opposed to a for loop or sum    def combs x       return  c for i in range len x  1  for c in combinations x i       Demo    gt  gt  gt  combs  1 2 3 4           1     2     3     4       1  2    1  3    1  4    2  3    2  4    3  4      1  2  3    1  2  4    1  3  4    2  3  4      1  2  3  4

User · Answer

If someone is looking for a reversed list  like I was   stuff    1  2  3  4   def reverse bla  y       for subset in itertools combinations bla  len bla -y           print list subset      if y    len bla           y    1         reverse bla  y   reverse stuff  1

User · Answer

This one-liner gives you all the combinations  between 0 and n items if the original list set contains n distinct elements  and uses the native method itertools combinations   Python 2  from itertools import combinations  input     a    b    c    d    output   sum  map list  combinations input  i   for i in range len input    1          Python 3  from itertools import combinations  input     a    b    c    d    output   sum  list map list  combinations input  i    for i in range len input    1            The output will be           a       b       c       d       a    b       a    c       a    d       b    c       b    d       c    d       a    b    c       a    b    d       a    c    d       b    c    d       a    b    c    d        Try it online   http   ideone com COghfX

User · Answer

This code employs a simple algorithm with nested lists       FUNCTION getCombos  To generate all combos of an input list  consider the following sets of nested lists                                                      A                               A   B                A B                               A   B   C            A B   A C   B C                          A B C                               A   B   C   D        A B   A C   B C   A D   B D   C D        A B C   A B D   A C D   B C D        A B C D           There is a set of lists for each number of items that will occur in a combo  including an empty set      For each additional item  begin at the back of the list by adding an empty list  then taking the set of    lists in the previous column  e g   in the last list  for sets of 3 items you take the existing set of    3-item lists and append to it additional lists created by appending the item  4  to the lists in the    next smallest item count set  In this case  for the three sets of 2-items in the previous list  Repeat    for each set of lists back to the initial list containing just the empty list     def getCombos listIn     A   B   C   D   E   F          listCombos                    list of lists of combos  seeded with a list containing only the empty list     listSimple                    list to contain the final returned list of items  e g   characters       for item in listIn          listCombos append         append an emtpy list to the end for each new item added         for index in xrange len listCombos -1  0  -1      set the index range to work through the list             for listPrev in listCombos index-1            retrieve the lists from the previous column                 listCur   listPrev                        create a new temporary list object to update                 listCur append item                       add the item to the previous list to make it current                 listCombos index  append listCur          list length and append it to the current list                  itemCombo                                 Create a str to concatenate list items into a str                 for item in listCur                       concatenate the members of the lists to create                     itemCombo    item                     create a string of items                 listSimple append itemCombo               add to the final output list      return  listSimple  listCombos    END getCombos

User · Answer

As stated in the documentation def combinations iterable  r         combinations  ABCD   2  -- gt  AB AC AD BC BD CD       combinations range 4   3  -- gt  012 013 023 123     pool   tuple iterable      n   len pool      if r  gt  n          return     indices   list range r       yield tuple pool i  for i in indices      while True          for i in reversed range r                if indices i     i   n - r                  break         else              return         indices i     1         for j in range i 1  r               indices j    indices j-1    1         yield tuple pool i  for i in indices    x    2  3  4  5  1  6  4  7  8  3  9  for i in combinations x  2       print i

User · Answer

Here s a lazy one-liner  also using itertools   from itertools import compress  product  def combinations items       return   set compress items mask   for mask in product    0 1   len items           alternative                          in product  0 1   repeat len items       Main idea behind this answer  there are 2 N combinations -- same as the number of binary strings of length N  For each binary string  you pick all elements corresponding to a  1    items abc   mask         V 000 - gt   001 - gt    c 010 - gt   b 011 - gt   bc 100 - gt  a 101 - gt  a c 110 - gt  ab 111 - gt  abc   Things to consider    This requires that you can call len      on items  workaround  if items is something like an iterable like a generator  turn it into a list first with items list  itemsArg   This requires that the order of iteration on items is not random  workaround  don t be insane  This requires that the items are unique  or else  2 2 1  and  2 1 1  will both collapse to  2 1   workaround  use collections Counter as a drop-in replacement for set  it s basically a multiset    though you may need to later use tuple sorted Counter      elements     if you need it to be hashable      Demo   gt  gt  gt  list combinations range 4     set     3    2    2  3    1    1  3    1  2    1  2  3    0    0  3    0  2    0  2  3    0  1    0  1  3    0  1  2    0  1  2  3     gt  gt  gt  list combinations  abcd     set      d      c      c    d      b      b    d      c    b      c    b    d      a      a    d      a    c      a    c    d      a    b      a    b    d      a    c    b      a    c    b    d

User · Answer

Have a look at itertools combinations    itertools combinations iterable  r        Return r length subsequences of elements from   the input iterable       Combinations are emitted in lexicographic sort order  So  if the   input iterable is sorted  the   combination tuples will be produced in   sorted order    Since 2 6  batteries are included

User · Answer

This is an approach that can be easily transfered to all programming languages supporting recursion  no itertools  no yield  no list comprehension    def combs a       if len a     0          return          cs          for c in combs a 1             cs     c  c  a 0        return cs   gt  gt  gt  combs  1 2 3 4 5         1    2    2  1    3    3  1    3  2         5  4  3  2  1

User · Answer

I m late to the party but would like to share the solution I found to the same issue  Specifically  I was looking to do sequential combinations  so for  quot STAR quot  I wanted  quot STAR quot    quot TA quot    quot AR quot   but not  quot SR quot   lst    S  T  A  R  lstCombos      for Length in range 0 len lst  1       for i in lst          lstCombos append lst lst index i  lst index i  Length    Duplicates can be filtered with adding in an additional if before the last line  lst    S  T  A  R  lstCombos      for Length in range 0 len lst  1       for i in lst           if not lst lst index i  lst index i  Length   in lstCombos               lstCombos append lst lst index i  lst index i  Length    If for some reason this returns blank lists in the output  which happened to me  I added  for subList in lstCombos      if subList                lstCombos remove subList

User · Answer

Here are two implementations of itertools combinations  One that returns a list  def combinations lst  depth  start 0  items          if depth  lt   0          return  items      out          for i in range start  len lst            out    combinations lst  depth - 1  i   1  items    lst i        return out   One returns a generator  def combinations lst  depth  start 0  prepend          if depth  lt   0          yield prepend     else          for i in range start  len lst                for c in combinations lst  depth - 1  i   1  prepend    lst i                     yield c   Please note that providing a helper function to those is advised because the prepend argument is static and is not changing with every call  print  c for c in combinations  1  2  3  4   3        1  2  3    1  2  4    1  3  4    2  3  4      get a hold of prepend prepend    c for c in combinations     -1   0  prepend append None   print  c for c in combinations  1  2  3  4   3        None  1  2  3    None  1  2  4    None  1  3  4    None  2  3  4     This is a very superficial case but better be safe than sorry

User · Answer

Here is yet another solution  one-liner   involving using the itertools combinations function  but here we use a double list comprehension  as opposed to a for loop or sum    def combs x       return  c for i in range len x  1  for c in combinations x i       Demo    gt  gt  gt  combs  1 2 3 4           1     2     3     4       1  2    1  3    1  4    2  3    2  4    3  4      1  2  3    1  2  4    1  3  4    2  3  4      1  2  3  4

User · Answer

As stated in the documentation def combinations iterable  r         combinations  ABCD   2  -- gt  AB AC AD BC BD CD       combinations range 4   3  -- gt  012 013 023 123     pool   tuple iterable      n   len pool      if r  gt  n          return     indices   list range r       yield tuple pool i  for i in indices      while True          for i in reversed range r                if indices i     i   n - r                  break         else              return         indices i     1         for j in range i 1  r               indices j    indices j-1    1         yield tuple pool i  for i in indices    x    2  3  4  5  1  6  4  7  8  3  9  for i in combinations x  2       print i

User · Answer

In comments under the highly upvoted answer by  Dan H  mention is made of the powerset   recipe in the itertools documentation   including one by Dan himself  However  so far no one has posted it as an answer  Since it s probably one of the better if not the best approach to the problem   and given a little encouragement from another commenter  it s shown below  The function produces all unique combinations of the list elements of every length possible  including those containing zero and all the elements    Note  If the  subtly different  goal is to obtain only combinations of unique elements  change the line s   list iterable  to s   list set iterable   to eliminate any duplicate elements  Regardless  the fact that the iterable is ultimately turned into a list means it will work with generators  unlike several of the other answers    from itertools import chain  combinations  def powerset iterable        powerset  1 2 3   -- gt      1    2    3    1 2   1 3   2 3   1 2 3       s   list iterable     allows duplicate elements     return chain from iterable combinations s  r  for r in range len s  1    stuff    1  2  3  for i  combo in enumerate powerset stuff   1       print  combo          format i  combo     Output   combo  1     combo  2   1   combo  3   2   combo  4   3   combo  5   1  2  combo  6   1  3  combo  7   2  3  combo  8   1  2  3

User · Answer

You can also use the powerset function from the excellent more itertools package   from more itertools import powerset  l    1 2 3  list powerset l            1     2     3     1  2    1  3    2  3    1  2  3     We can also verify  that it meets OP s requirement  from more itertools import ilen  assert ilen powerset range 15       32 768

[python] How to get all possible combinations of a list’s elements?

Examples related to python

Examples related to combinations