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

1
votes

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.

2
pythonnumpyvectorpowerset
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 codereview.stackexchange.com – tamasgal
@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
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
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
Closer to stackoverflow.com/q/1208118/102441 I think, since the numpy distinction is important – Eric

2 Answers

1
votes

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)
0
votes

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]]