Get the cartesian product of a series of lists

Question

How can I get the Cartesian product  every possible combination of values  from a group of lists   Input    somelists         1  2  3        a    b        4  5      Desired output     1   a   4    1   a   5    1   b   4    1   b   5    2   a   4    2   a   5

User · Answer

Here is a recursive generator  which doesn t store any temporary lists  def product ar list       if not ar list          yield        else          for a in ar list 0               for prod in product ar list 1                     yield  a   prod  print list product   1 2   3 4   5 6       Output     1  3  5    1  3  6    1  4  5    1  4  6    2  3  5    2  3  6    2  4  5    2  4  6

User · Answer

I believe this works   def cartesian product L        if L         return   a     b for a in L 0                           for b in cartesian product L 1        else         return

User · Answer

You can use itertools product in the standard library to get the cartesian product  Other cool  related utilities in itertools include permutations  combinations  and combinations with replacement  Here is a link to a python codepen for the snippet below  from itertools import product  somelists         1  2  3        a    b        4  5     result   list product  somelists   print result

User · Answer

I would use list comprehension     somelists         1  2  3        a    b        4  5     cart prod     a b c  for a in somelists 0  for b in somelists 1  for c in somelists 2

User · Answer

Recursive Approach   def rec cart start  array  partial  results     if len partial     len array       results append partial      return     for element in array start       rec cart start 1  array  partial  element   results   rec res      some lists     1  2  3     a    b     4  5     rec cart 0  some lists      rec res  print rec res    Iterative Approach   def itr cart array     results          for i in range len array        temp          for res in results        for element in array i           temp append res  element       results   temp    return results  some lists     1  2  3     a    b     4  5     itr res   itr cart some lists  print itr res

User · Answer

In Python 2 6 and above you can use  itertools product   In older versions of Python you can use the following  almost -- see documentation  equivalent code from the documentation  at least as a starting point   def product  args    kwds         product  ABCD    xy   -- gt  Ax Ay Bx By Cx Cy Dx Dy       product range 2   repeat 3  -- gt  000 001 010 011 100 101 110 111     pools   map tuple  args    kwds get  repeat   1      result            for pool in pools          result    x  y  for x in result for y in pool      for prod in result          yield tuple prod    The result of both is an iterator  so if you really need a list for furthert processing  use list result

User · Answer

Although there are many answers already  I would like to share some of my thoughts   Iterative approach  def cartesian iterative pools     result          for pool in pools      result    x  y  for x in result for y in pool    return result   Recursive Approach  def cartesian recursive pools     if len pools   gt  2      pools 0    product pools 0   pools 1       del pools 1      return cartesian recursive pools    else      pools 0    product pools 0   pools 1       del pools 1      return pools def product x  y     return  xx    yy  if isinstance xx  list  else  xx     yy  for xx in x for yy in y    Lambda Approach  def cartesian reduct pools     return reduce lambda x y  product x y    pools

User · Answer

import itertools  gt  gt  gt  for i in itertools product  1 2 3    a   b    4 5                print i      1   a   4   1   a   5   1   b   4   1   b   5   2   a   4   2   a   5   2   b   4   2   b   5   3   a   4   3   a   5   3   b   4   3   b   5   gt  gt  gt

User · Answer

For Python 2 5 and older    gt  gt  gt    a  b  c  for a in  1 2 3  for b in   a   b   for c in  4 5     1   a   4    1   a   5    1   b   4    1   b   5    2   a   4      2   a   5    2   b   4    2   b   5    3   a   4    3   a   5      3   b   4    3   b   5     Here s a recursive version of product    just an illustration    def product  args       if not args          return iter          yield tuple       return  items    item                for items in product  args  -1   for item in args -1     Example    gt  gt  gt  list product  1 2 3     a   b     4 5       1   a   4    1   a   5    1   b   4    1   b   5    2   a   4      2   a   5    2   b   4    2   b   5    3   a   4    3   a   5      3   b   4    3   b   5    gt  gt  gt  list product  1 2 3      1     2     3     gt  gt  gt  list product          gt  gt  gt  list product

User · Answer

Stonehenge approach   def giveAllLists a  t       if  t   1    len a            x              for i in a t               p    i              x append p          return x     x           out   giveAllLists a  t   1      for i in a t            for j in range len out                p    i              for oz in out j                   p append oz              x append p      return x  xx    1 2 3   22 34  se     k    print giveAllLists xx  0       output     1  22   k     1  34   k     1   se    k     2  22   k     2  34   k     2   se    k     3  22   k     3  34   k     3   se    k

User · Answer

With early rejection  def my product pools  List List Any    rules  Dict Any  List Any    forbidden  List Any   - gt  Iterator Tuple Any         quot  quot  quot      Compute the cartesian product except it rejects some combinations based on provided rules           param pools  the values to calculate the Cartesian product on       param rules  a dict specifying which values each value is incompatible with      param forbidden  values that are never authorized in the combinations      return  the cartesian product      quot  quot  quot      if not pools          return      included   set          if an element has an entry of 0  it s acceptable  if greater than 0  it s rejected  cannot be negative     incompatibles   defaultdict int      for value in forbidden          incompatibles value     1     selections    -1    len pools      pool idx   0      def current value            return pools pool idx  selections pool idx        while True            Discard incompatibilities from value from previous iteration on same pool         if selections pool idx   gt   0              for value in rules current value                     incompatibles value  -  1             included discard current value               Try to get to next value of same pool         if selections pool idx     len pools pool idx   - 1              selections pool idx     1           Get to previous pool if current is exhausted         elif pool idx    0              selections pool idx    - 1             pool idx -  1             continue           Done if first pool is exhausted         else              break            Add incompatibilities of newly added value         for value in rules current value                 incompatibles value     1         included add current value               Skip value if incompatible         if incompatibles current value    or                   any intersection in included for intersection in rules current value                  continue            Submit combination if we re at last pool         if pools pool idx     pools -1               yield tuple pool selection  for pool  selection in zip pools  selections             Else get to next pool         else              pool idx    1  I had a case where I had to fetch the first result of a very big Cartesian product  And it would take ages despite I only wanted one item  The problem was that it had to iterate through many unwanted results before finding a correct one because of the order of the results  So if I had 10 lists of 50 elements and the first element of the two first lists were incompatible  it had to iterate through the Cartesian product of the last 8 lists despite that they would all get rejected  This implementation enables to test a result before it includes one item from each list  So when I check that an element is incompatible with the already included elements from the previous lists  I immediately go to the next element of the current list rather than iterating through all products of the following lists

User · Answer

A minor modification to the above recursive generator solution in variadic flavor   def product args  args       if args          for a in args 0               for prod in product args  args 1    if args 1   else                        yield  a     prod   And of course a wrapper which makes it work exactly the same as that solution   def product2 ar list                gt  gt  gt  list product                    gt  gt  gt  list product2                         return product args  ar list    with one trade-off  it checks if recursion should break upon each outer loop  and one gain  no yield upon empty call  e g product      which I suppose would be semantically more correct  see the doctest    Regarding list comprehension  the mathematical definition applies to an arbitrary number of arguments  while list comprehension could only deal with a known number of them

User · Answer

with itertools product   import itertools result   list itertools product  somelists

User · Answer

itertools product  Available from Python 2 6   import itertools  somelists         1  2  3        a    b        4  5    for element in itertools product  somelists       print element    Which is the same as   for element in itertools product  1  2  3     a    b     4  5        print element

User · Answer

Just to add a bit to what has already been said  if you use sympy  you can use symbols rather than strings which makes them mathematically useful   import itertools import sympy  x  y   sympy symbols  x y    somelist     x y    1 2 3    4 5   somelist2     1 2    1 2 3    4 5    for element in itertools product  somelist     print element   About sympy

[python] Get the cartesian product of a series of lists?

Examples related to python

Examples related to list

Examples related to cartesian-product