5

Given an array a=['a','b','c'], how would you go about returning the Cartesian product of the array without duplicates. Example: 

[['a', 'a' , 'a' ,'a']
['a', 'a' , 'a' ,'b']
['a', 'a' , 'a' ,'c']
['a', 'a' , 'b' ,'b']
['a', 'a' , 'b' ,'c']
['a', 'a' , 'c' ,'c']
...etc..]

Following How to generate all permutations of a list in Python, I tried : 

print list(itertools.permutations(['a', 'b' , 'c'], 4))
[]

print list(itertools.product(['a', 'b' , 'c'], repeat=4)

But I get the Cartesian product with duplicates. For example the list will contain both ['a','a','b','b'] and ['a','b','b','a'] which are clearly the equal.

Note: my 'a','b','c' are variables which store numbers say 1,2,3. So after getting the list of combinations of the letters, I would need to: say,

['a','b','c','c'] ----> a*b*c*c = 1*2*3*3 = 18

What is the fastest way of doing this in python? Would it be possible/faster to do it with numpy?? Thanks!

Community
  • 1
  • 1
Oniropolo
  • 879
  • 2
  • 12
  • 18

2 Answers2

11

Maybe you actually want combinations_with_replacement?

>>> from itertools import combinations_with_replacement
>>> a = ['a', 'b', 'c']
>>> c = combinations_with_replacement(a, 4)
>>> for x in c:
...     print x
...     
('a', 'a', 'a', 'a')
('a', 'a', 'a', 'b')
('a', 'a', 'a', 'c')
('a', 'a', 'b', 'b')
('a', 'a', 'b', 'c')
('a', 'a', 'c', 'c')
('a', 'b', 'b', 'b')
('a', 'b', 'b', 'c')
('a', 'b', 'c', 'c')
('a', 'c', 'c', 'c')
('b', 'b', 'b', 'b')
('b', 'b', 'b', 'c')
('b', 'b', 'c', 'c')
('b', 'c', 'c', 'c')
('c', 'c', 'c', 'c')

Without more information about how you're mapping strings to numbers I can't comment on your second question, but writing your own product function or using numpy's isn't too difficult.

DSM
  • 342,061
  • 65
  • 592
  • 494
-1

Edit: Don't use this; use the other answer

If your original set is guaranteed uniqueness, then the `combinations_with_replacement` solution will work. If not, you can first pass it through `set()` to get it down to unique variables. Regarding the product, assuming you have the values stored in a dictionary `values` and that all the variables are valid python identifiers, you can do something like the following 
combos = combinations_with_replacement(a, 4)
product_strings = ['*'.join(c) for c in combos]
products = [eval(s, globals(), values) for s in product_strings]

Needless to say, be very careful with eval. Only use this solution if you are creating the list a.

Example exploit: a = ['from os import', '; system("rm -rf .");']

Felipe
  • 3,003
  • 2
  • 26
  • 44
  • i dont get what does eval(s, globals(), values) do ?? – Oniropolo May 07 '13 at 20:42
  • The string you're passing in is something like `"a*b*c*d"`. When you `eval` it, the second argument is a local dictionary to use. Eg, `{'a': 2, 'b': 3, 'c': 1, 'd': 1}`. It tells python the values of each of your variables. – Felipe May 08 '13 at 03:56
  • 1
    To anyone reading this answer in the future (since it's the top answer): any time you are thinking of using `eval`, pump the brakes. It's generally a bad idea. Use the other answer. – AmphotericLewisAcid Apr 12 '21 at 23:53