Creating the Cartesian Product of a set of Vectors in Python?

Question

Given the standard basis vectors (e_1,e_2,e_3) in 3 dimensions and letting the elements of (e_1,e_2,e_3) be restricted to, say (0,1,2,3,4) is there a simple pythonic way to create the cartesian product of all the vectors in this vector space?

For example, given [1,0,0],[0,1,0] and [0,0,1], I would like to get a list of all of the linear combinations (where the a_i's are restricted to the naturals between 0 and 4) of these vectors between [0,0,0] and [4,4,4].

I could program this up myself but before going to that trouble I thought I would ask if there is a simple pythonic way of doing it, maybe in numpy or something similar.

The best way is to "go[...] to that trouble" and learn something. If you encounter any problem, come back. If you solved your problem you're fine. If you're not satisfied with it, go to http://codereview.stackexchange.com — tamasgal, May 19 '15 at 19:45
@septi Thanks for the reply but I also wanted to see as well if there were any built-in functions that did this. I find it helps to ask around and get ideas before trying to do something that seems to me like reinventing the wheel. Also as this is something that seems fairly common to me I think this might help future others who might stumble upon this. I think it is a perfectly valid question. Sorry if you don't think so. — sfortney, May 19 '15 at 19:51
I'm pretty sure that there is no ready-to-use function for this specific problem. However, as you found out, there is `itertools` and `numpy` is great for vectors and matrices. So learn how to use them and I'm sure you'll figure out a nice solution. — tamasgal, May 19 '15 at 19:56
Sounds like you just want `itertools.product((0,1,2,3,4), repeat=3)`. You're describing the cartesian product, not the power set — Eric, May 19 '15 at 20:26
You are correct. Though the two concepts are similar, the cartesian product is the mathematically correct definition. And your answer is an excellent way of doing this. Now that you say that this could be marked as a dup of http://stackoverflow.com/questions/533905/get-the-cartesian-product-of-a-series-of-lists-in-python — sfortney, May 19 '15 at 20:36
Closer to http://stackoverflow.com/q/1208118/102441 I think, since the numpy distinction is important — Eric, May 19 '15 at 20:38

score 1 · Accepted Answer · answered May 19 '15 at 20:31

For the specific case of a space of natural numbers, you want np.indices:

>>> np.indices((4, 4)).reshape(2,-1).T
array([[0, 0],
       [0, 1],
       [0, 2],
       [0, 3],
       [1, 0],
       [1, 1],
       [1, 2],
       [1, 3],
       [2, 0],
       [2, 1],
       [2, 2],
       [2, 3],
       [3, 0],
       [3, 1],
       [3, 2],
       [3, 3]])

(numpy actually outputs these in a grid, but you wanted a 1-D list of points, hence the .reshape)

Otherwise, what you're describing is not a powerset but a cartesian product

itertools.product(range(4), repeat=3)

sfortney · Answer 2 · 2015-05-19T20:44:11.790

Edit: This answer works but I think Eric's is better because it is more easily generalizable.

In the interest of helping others who might stumble upon this question. Here is a very simple way of doing the above question. It employs np.where to find all the indices of a matrix meeting a certain criteria. Here, our criteria is just something that is satisfied by all of the matrix. This is equivalent to the problem above. This only holds for the example as stated above but it shouldn't be too difficult to generalize this up to N dimensions.

import numpy as np
dim=3
gran=5

def vec_powerset(dim, gran):
    #returns a list of all the vectors for a three dimensional vector space
    #where the elements of the vectors are the naturals up to gran

    size=tuple([gran]*dim)
    a=np.zeros(size)

    return [[np.where(a>(-np.inf))[0][x],np.where(a>(-np.inf))[1][x],
    np.where(a>(-np.inf))[2][x]] for x in
    range(len(np.where(a>(-np.inf))[0]))]

print vec_powerset(dim,gran)

[[0, 0, 0], [0, 0, 1], [0, 0, 2], [0, 0, 3], [0, 0, 4], [0, 1, 0], [0, 1, 1], [0, 1, 2], [0, 1, 3], [0, 1, 4], [0, 2, 0], [0, 2, 1], [0, 2, 2], [0, 2, 3], [0, 2, 4], [0, 3, 0], [0, 3, 1], [0, 3, 2], [0, 3, 3], [0, 3, 4], [0, 4, 0], [0, 4, 1], [0, 4, 2], [0, 4, 3], [0, 4, 4], [1, 0, 0], [1, 0, 1], [1, 0, 2], [1, 0, 3], [1, 0, 4], [1, 1, 0], [1, 1, 1], [1, 1, 2], [1, 1, 3], [1, 1, 4], [1, 2, 0], [1, 2, 1], [1, 2, 2], [1, 2, 3], [1, 2, 4], [1, 3, 0], [1, 3, 1], [1, 3, 2], [1, 3, 3], [1, 3, 4], [1, 4, 0], [1, 4, 1], [1, 4, 2], [1, 4, 3], [1, 4, 4], [2, 0, 0], [2, 0, 1], [2, 0, 2], [2, 0, 3], [2, 0, 4], [2, 1, 0], [2, 1, 1], [2, 1, 2], [2, 1, 3], [2, 1, 4], [2, 2, 0], [2, 2, 1], [2, 2, 2], [2, 2, 3], [2, 2, 4], [2, 3, 0], [2, 3, 1], [2, 3, 2], [2, 3, 3], [2, 3, 4], [2, 4, 0], [2, 4, 1], [2, 4, 2], [2, 4, 3], [2, 4, 4], [3, 0, 0], [3, 0, 1], [3, 0, 2], [3, 0, 3], [3, 0, 4], [3, 1, 0], [3, 1, 1], [3, 1, 2], [3, 1, 3], [3, 1, 4], [3, 2, 0], [3, 2, 1], [3, 2, 2], [3, 2, 3], [3, 2, 4], [3, 3, 0], [3, 3, 1], [3, 3, 2], [3, 3, 3], [3, 3, 4], [3, 4, 0], [3, 4, 1], [3, 4, 2], [3, 4, 3], [3, 4, 4], [4, 0, 0], [4, 0, 1], [4, 0, 2], [4, 0, 3], [4, 0, 4], [4, 1, 0], [4, 1, 1], [4, 1, 2], [4, 1, 3], [4, 1, 4], [4, 2, 0], [4, 2, 1], [4, 2, 2], [4, 2, 3], [4, 2, 4], [4, 3, 0], [4, 3, 1], [4, 3, 2], [4, 3, 3], [4, 3, 4], [4, 4, 0], [4, 4, 1], [4, 4, 2], [4, 4, 3], [4, 4, 4]]

You need to stop using the term "powerset" for this. It draws the wrong search hits. — Dzamo Norton, Aug 11 '16 at 18:59
I'll gladly edit if you give me a better term. I am aware it is incorrect but I couldn't think of a better way to say it. In the meantime I have put the title in quotations — sfortney, Aug 11 '16 at 20:54
You are forming a Cartesian Product. https://en.wikipedia.org/wiki/Cartesian_product — Dzamo Norton, Aug 12 '16 at 13:10

Creating the Cartesian Product of a set of Vectors in Python?

2 Answers2