Using Numpy to Build an Array of All Combinations of Two Arrays

Using numpy to build an array of all combinations of two arrays

In newer version of numpy (>1.8.x), numpy.meshgrid() provides a much faster implementation:

@pv's solution

In [113]:

%timeit cartesian(([1, 2, 3], [4, 5], [6, 7]))
10000 loops, best of 3: 135 µs per loop
In [114]:

cartesian(([1, 2, 3], [4, 5], [6, 7]))

Out[114]:
array([[1, 4, 6],
       [1, 4, 7],
       [1, 5, 6],
       [1, 5, 7],
       [2, 4, 6],
       [2, 4, 7],
       [2, 5, 6],
       [2, 5, 7],
       [3, 4, 6],
       [3, 4, 7],
       [3, 5, 6],
       [3, 5, 7]])

numpy.meshgrid() use to be 2D only, now it is capable of ND. In this case, 3D:

In [115]:

%timeit np.array(np.meshgrid([1, 2, 3], [4, 5], [6, 7])).T.reshape(-1,3)
10000 loops, best of 3: 74.1 µs per loop
In [116]:

np.array(np.meshgrid([1, 2, 3], [4, 5], [6, 7])).T.reshape(-1,3)

Out[116]:
array([[1, 4, 6],
       [1, 5, 6],
       [2, 4, 6],
       [2, 5, 6],
       [3, 4, 6],
       [3, 5, 6],
       [1, 4, 7],
       [1, 5, 7],
       [2, 4, 7],
       [2, 5, 7],
       [3, 4, 7],
       [3, 5, 7]])

Note that the order of the final resultant is slightly different.

Using numpy to build an array of all combinations of two arrays

In newer version of numpy (>1.8.x), numpy.meshgrid() provides a much faster implementation:

@pv's solution

In [113]:

%timeit cartesian(([1, 2, 3], [4, 5], [6, 7]))
10000 loops, best of 3: 135 µs per loop
In [114]:

cartesian(([1, 2, 3], [4, 5], [6, 7]))

Out[114]:
array([[1, 4, 6],
       [1, 4, 7],
       [1, 5, 6],
       [1, 5, 7],
       [2, 4, 6],
       [2, 4, 7],
       [2, 5, 6],
       [2, 5, 7],
       [3, 4, 6],
       [3, 4, 7],
       [3, 5, 6],
       [3, 5, 7]])

numpy.meshgrid() use to be 2D only, now it is capable of ND. In this case, 3D:

In [115]:

%timeit np.array(np.meshgrid([1, 2, 3], [4, 5], [6, 7])).T.reshape(-1,3)
10000 loops, best of 3: 74.1 µs per loop
In [116]:

np.array(np.meshgrid([1, 2, 3], [4, 5], [6, 7])).T.reshape(-1,3)

Out[116]:
array([[1, 4, 6],
       [1, 5, 6],
       [2, 4, 6],
       [2, 5, 6],
       [3, 4, 6],
       [3, 5, 6],
       [1, 4, 7],
       [1, 5, 7],
       [2, 4, 7],
       [2, 5, 7],
       [3, 4, 7],
       [3, 5, 7]])

Note that the order of the final resultant is slightly different.

Python - Find all possible combination between two arrays

If your purpose is to get x/y combinations for 3D plotting, what you're looking for is numpy.meshgrid

# input arrays
x = np.arange(1, 10)
y = np.arange(10, 100, 20)

# x = array([1, 2, 3, 4, 5, 6, 7, 8, 9])
# y = array([10, 30, 50, 70, 90])

# computing the meshgrid
X, Y = np.meshgrid(x,y)

output:

# X
array([[1, 2, 3, 4, 5, 6, 7, 8, 9],
       [1, 2, 3, 4, 5, 6, 7, 8, 9],
       [1, 2, 3, 4, 5, 6, 7, 8, 9],
       [1, 2, 3, 4, 5, 6, 7, 8, 9],
       [1, 2, 3, 4, 5, 6, 7, 8, 9]])

# Y
array([[10, 10, 10, 10, 10, 10, 10, 10, 10],
       [30, 30, 30, 30, 30, 30, 30, 30, 30],
       [50, 50, 50, 50, 50, 50, 50, 50, 50],
       [70, 70, 70, 70, 70, 70, 70, 70, 70],
       [90, 90, 90, 90, 90, 90, 90, 90, 90]])

Numpy: efficient way to generate combinations from given ranges

I think what you're looking for is np.mgrid. Unfortunately, this returns the array in a format that's different from what you need, so you'll need to do a little post-processing:

a = np.mgrid[0:4, 0:4, 0:11]     # All points in a 3D grid within the given ranges
a = np.rollaxis(a, 0, 4)         # Make the 0th axis into the last axis
a = a.reshape((4 * 4 * 11, 3))   # Now you can safely reshape while preserving order

Explanation

np.mgrid gives you a set of grid points in N-dimensional space. Let me try to show this with a smaller example, to make things clearer:

>>> a = np.mgrid[0:2, 0:2]
>>> a
array([[[0, 0],
        [1, 1]],

       [[0, 1],
        [0, 1]]])

Since I've given two sets of ranges, 0:2, 0:2, I get a 2D grid. What mgrid returns is the x-values and the y-values corresponding to the grid points (0, 0), (0, 1), (1, 0) and (1, 1) in 2D space. a[0] tells you what the x-values of the four points are, and a[1] tells you what the y-values are.

But what you really want is that list of actual grid points that I've written out, not the x- and y-values of those points separately. First instinct is to just reshape the array as desired:

>>> a.reshape((4, 2))
array([[0, 0],
       [1, 1],
       [0, 1],
       [0, 1]])

But clearly this doesn't work, because it effectively reshapes the flattened array (the array obtained by just reading all elements in order), and that's not what you want.

What you want to do is to look down the third dimension of a, and create an array:

[ [a[0][0, 0], a[1][0, 0]],
  [a[0][0, 1], a[1][0, 1]],
  [a[0][1, 0], a[1][1, 0]],
  [a[0][1, 1], a[1][1, 1]] ]

which reads "First tell me the first point (x1, y1), then the second point (x2, y2), ..." and so on. Perhaps this is better explained with a figure, of sorts. This is what a looks like:

                you want to read
                in this direction
                 (0, 0)   (0, 1)
                   |        |
                   |        |
                   v        v

          /        0--------0            +----> axis0
 x-values |       /|       /|           /|
          |      / |      / |    axis1 / |
          \     1--------1  |         L  |
                |  |     |  |            v
          /     |  0-----|--1           axis2
 y-values |     | /      | /
          |     |/       |/
          \     0--------1

                |        |
                |        |
                v        v
              (1, 0)   (1, 1)

np.rollaxis gives you a way to do this. np.rollaxis(a, 0, 3) in the above example says "take the 0th (or outermost) axis and make it into the last (or innermost) axis. (Note: only axes 0, 1 and 2 actually exist here. So saying "send the 0th axis to the 3rd position" is a way of telling python to put the 0th axis after the last axis). You might also want to read this.

>>> a = np.rollaxis(a, 0, 3)
>>> a
array([[[0, 0],
        [0, 1]],

       [[1, 0],
        [1, 1]]])

This is starting to look like what you want, except there's an extra array dimension. We want to merge dimensions 0 and 1 to get just get a single array of grid points. But now that the flattened array reads in the manner that you expect, you can safely reshape it to give you the desired result.

>>> a = a.reshape((4, 2))
>>> a
array([[0, 0],
       [0, 1],
       [1, 0],
       [1, 1]])

The 3D version does just the same thing, except, I couldn't make a figure for that, since it'd be in 4D.

Numpy - Product of All Unique Combinations or Paths along an axis

One solution is to use itertools to generate all the possible indices and then use Numpy indirect indexing so to extract the actual paths:

a = np.array([[1, 2, 3,  4,  5,  6],
              [7, 8, 9, 10, 11, 12]])

rowCount = a.shape[0]**a.shape[1]
x = np.tile(np.arange(a.shape[1]), rowCount).reshape(-1, a.shape[1])
y = np.array(list(itertools.product(*[range(2)]*6)))
result = a[y, x]
product = np.prod(a[y, x], axis=-1)

Note that this solution is not very efficient with bigger arrays. In fact, as said in the comment, the number of possible paths grows exponentially (n**m where n, m = a.shape) and thus the required memory space grow in O(n**m * m). Even the size of the output product grows experientially (n**m).

All binary combinations in a 2d Numpy

Here is a vectorized solution that can work for small matrix sizes; comments in the code illustrate a 3 by 3 case:

def get_binary_mats(n):
  # all possible n by n binary matrices up to rotation: 
  bin_mats = (np.bitwise_and(np.arange(2**(n*n))[:,None], 2 ** np.arange(n*n)) > 0)\
    .reshape(-1, n, n)
  # define a score for each matrix based on position of ones
  score = 2 ** np.arange(n*n).reshape(n,n)
  # array([[  1,   2,   4],
        #  [  8,  16,  32],
        #  [ 64, 128, 256]])
  score_arr = np.stack([np.rot90(score, k=k) for k in range(4)])
  # array([[[  1,   2,   4],
  #         [  8,  16,  32],
  #         [ 64, 128, 256]],

  #        [[  4,  32, 256],
  #         [  2,  16, 128],
  #         [  1,   8,  64]],

  #        [[256, 128,  64],
  #         [ 32,  16,   8],
  #         [  4,   2,   1]],

  #        [[ 64,   8,   1],
  #         [128,  16,   2],
  #         [256,  32,   4]]])

  scores = np.einsum("ijk,ljk->il", bin_mats, score_arr)
  _, idx = np.unique(scores.min(1), return_index=True)
  return bin_mats[idx,...]

The main idea is that we can take a "dot product" of an N by N binary matrix with an N by N matrix consisting of first N^2 powers of 2 (I call the latter the score matrix). When we do this, we get a unique integer for each possible binary matrix.

To account for rotations, we can take a "dot product" with 4 rotations of the "score" matrix, and associate each binary matrix to the minimum of the four results. We can refer to this minimum as a score of a binary matrix.

Finally, we can pick a matrix for each unique score with np.unique. For example, here is the output for n = 2:

array([[[False, False],
        [False, False]],

       [[ True, False],
        [False, False]],

       [[ True,  True],
        [False, False]],

       [[False,  True],
        [ True, False]],

       [[ True,  True],
        [ True, False]],

       [[ True,  True],
        [ True,  True]]])

As a sanity check, the number of binary matrices up to rotation lines up with this OEIS sequence for n up to 5:

%time assert [get_binary_mats(k).shape[0] for k in range(1, 6)] == [2, 6, 140, 16456, 8390720]
# takes 20 seconds on my machine

python efficiently applying function over multiple arrays

Use numpy.meshgrid to make an array of all the combinations of values of the three variables.

products = np.array(np.meshgrid(accuracy, tranChance, numChoices)).T.reshape(-1, 3)

Then transpose this again and extract three longer arrays with the values of the three variables in every combination:

accuracy_, tranChance_, numChoices_ = products.T

Your function contains only operations that can be carried out on numpy arrays, so you can then simply feed these arrays as parameters into the function:

reward = ??  # you need to set the reward value
results = plot_ev(accuracy_, tranChance_, numChoices_, reward)

Alternatively consider using a pandas dataframe which will provide clearer labeling of the columns.

import pandas as pd
df = pd.DataFrame(products, columns=["accuracy", "tranChance", "numChoices"])
df["ev"] = plot_ev(df["accuracy"], df["tranChance"], df["numChoices"], reward)

All possible combinations of 2D numpy array

Here is a numpy solution, based on the Cartesian product implementation from here.

arr = np.stack([a1, a2, a3, a4])

print(arr.shape) # (4, 6, 2)
n, m, k = arr.shape

# from https://stackoverflow.com/questions/11144513/cartesian-product-of-x-and-y-array-points-into-single-array-of-2d-points
def cartesian_product(*arrays):
    la = len(arrays)
    dtype = np.result_type(*arrays)
    arr = np.empty([len(a) for a in arrays] + [la], dtype=dtype)
    for i, a in enumerate(np.ix_(*arrays)):
        arr[...,i] = a
    return arr.reshape(-1, la)

inds = cartesian_product(*([np.arange(m)] * n))
res = np.take_along_axis(arr, inds.T[...,None], 1).swapaxes(0,1).reshape(-1, n*k)

print(res[0])
# [-24.4925 295.77   -26.0075 309.39   -25.5025 310.265  -27.0175 326.895 ]

In this example, the inds array looks as follows:

print(inds[:10])
# [[0 0 0 0]
#  [0 0 0 1]
#  [0 0 0 2]
#  [0 0 0 3]
#  [0 0 0 4]
#  [0 0 0 5]
#  [0 0 1 0]
#  [0 0 1 1]
#  [0 0 1 2]
#  [0 0 1 3]]

We can then use np.take_along_axis to select appropriate elements for each combination.

---

Related Topics