0

I have a numpy array like this:

[[1, 2], [1, 3], [2, 1], [2, 2], [2, 3], ...]

I would like to get the combinations of all "sub" arrays (i.e [X, Y]) three by three:

[[1, 1] [1, 1] [1, 1],
 [1, 1] [1, 1] [1, 2],
 [1, 1] [1, 1] [1, 3],
 ...
 [5, 5] [5, 5], [5, 4],
 [5, 5] [5, 5], [5, 5]]

Then, I need to apply conditions on each combinations:

  • X1, X2, X3 > 0
  • X1+Y1 <= X2
  • X2+Y2 <= X3
  • [X1, Y1] =! [X2, Y2]
  • [X2, Y2] =! [X3, Y3]
  • ...

I absolutely need to avoid for loops because of the high number of combinations.

Any idea how to get this done in an effective time of execution?

My current code with for loops and if statements:

The mylist object is like [[1, 1], [1, 2], [2, 1], ...] (i.e list of lists like [X, Y]).

Combination = [] for left in mylist:

    if left[0] > 0:
        
        for center in mylist:   
            
            if (center[0] > 0 
                and center[0] >= left[0] + left[1]
                and center[1] / left[1] < 2 
                and center[0] / left[0] < 2
                and left[1] / center[1] < 2 
                and left[0] / center[1] < 2 
                and str(left[0]) + "y" + str(left[1]) + "y" != str(center[0]) + "y" + str(center[1]) + "y"
                ):
            
                for right in mylist:   
        
                    if (right[0] > 0 
                        and right[0] >= center[0] + center[1]
                        and right[1] / center[1] < 2 
                        and right[0] / center[0] < 2
                        and center[1] / right[1] < 2 
                        and center[0] / right[0] < 2
                        and str(right[0]) + "y" + str(right[1]) + "y" != str(center[0]) + "y" + str(center[1]) + "y"
                        ):

                        Combination.append([[left[0], left[1]], [center[0], center[1]], [right[0], right[1]])
Community
  • 1
  • 1
ZottoZ
  • 43
  • 1
  • 6

3 Answers3

1

Try itertool and numpy like:

import numpy as np
import itertools


some_list = [[1, 2], [1, 3], [2, 1], [2, 2], [2, 3], [-1,-1]]


# use "itertools.combinations" or "itertools.combinations_with_replacement"
# whatever you want to get in therms of repeting elements.
# Then cast it into a numpy array.
combinations = np.array(list(itertools.combinations_with_replacement(some_list, 3)))


# from here your can do your boolean statements in the numpy sytax for example
# applying your first rule "X1,X2,X3 > 0" could be done with:
first_rule = combinations[:,:,0] > 0
print('boolean array for the first rule "X1,X2,X3 > 0"')
print(np.all(first_rule,axis=1))


# and the second rule "X1 + Y1 <= X2"
second_rule = combinations[:,0,0]+combinations[:,0,1] <= combinations[:,1,0]
print('\n\nboolean array for the first rule "X1 + Y1 <= X2"')
print(second_rule)

I assumed that its not just a regular grid because of the first condition X1,X2,X3 > 0, but yes if its regular then the meshgrid is the best solution (see the other answer).

some_name.py
  • 777
  • 5
  • 16
  • Great solution for efficient application of conditions. For creating the combinations though, it would be better to use `np.meshgrid()` as [creating a numpy array from a python list is slow.](https://stackoverflow.com/questions/33282369/convert-itertools-array-into-numpy-array) – emilanov Aug 20 '19 at 11:04
  • Very true but I am not sure if it is a regular grid and if so this has only have to applied once and then can be saved. But ofc `np.meshgird` is the far more elegant solution. – some_name.py Aug 20 '19 at 11:10
0

Edit: You don't even need itertools you can use numpy to create the combinations and it's extremely fast

# This is your input array from [1,1] to [5,5]
a = np.array(np.meshgrid(np.arange(1,6), np.arange(1,6))).T.reshape(-1,2)

b = np.array(np.meshgrid(a, a, a)).T.reshape(-1, 3, 2)

As you can see it takes 6ms: 5.88 ms ± 836 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

Your array looks like this now:


array([[[1, 1],
        [1, 1],
        [1, 1]],

       [[1, 1],
        [1, 1],
        [1, 2]],

       [[1, 1],
        [1, 1],
        [1, 3]],

       ...,

       [[5, 5],
        [5, 5],
        [5, 3]],

       [[5, 5],
        [5, 5],
        [5, 4]],

       [[5, 5],
        [5, 5],
        [5, 5]]])

Because this is a numpy array now, you can safely use a for loop to check your conditions. For example row[0,0] would be your X1 and row[0,1] would be your Y1 etc.

for row in b:
    row[0,0] + row[0,1] <= row[1,0]

This also takes a really short amount of time to execute: 10.3 ms ± 278 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

So you can safely do this for your other conditions aswell.

emilanov
  • 362
  • 4
  • 15
  • 1
    Mixing the Mashudan's and emilanov answers, I get exactly what I was looking for! Thank you a lot – ZottoZ Aug 20 '19 at 18:56
0

from itertools import product a = [[1,1],[1, 2], [1, 3], [2, 1], [2, 2], [2, 3]] perms = np.array(list(product(a, repeat=3))) This will create an array of shape (n^3, 3, 2) where n is the number of elements in a.

Now you can do all your fancy operations...

perms[:, :, 0] > 0
perms[:, 0, 0] + perms[:, 0, 1] <= perms[:, 1, 0]
perms[:, 1, 0] + perms[:, 1, 1] <= perms[:, 2, 0]
perms[:, 0, :] != perms[:, 1, :]
perms[:, 1, :] != perms[:, 2, :]
...

note that the last two expression will check x1!=x2 and y1!=y2 seperately and return a result of shape (n^3,2). However if your requirement is to check whether those instances are not equal as a whole you can just do

output = perms[:, 0, :] != perms[:, 1, :] np.logical_or(output[:, 0], output[:, 1])

which will return the output with shape (n^3).

Madushan
  • 31
  • 3