Combinaciones sin repetición y ordenamiento de materias o permutaciones de elementos de matriz.

Para una matriz 1D NumPy, busco obtener las combinaciones sin que se repitan los mismos elementos en una combinación. El orden es importante. Entonces, [a,b] y [b,a] serían dos combinaciones distintas. Como no queremos repeticiones, [a,a] y [b,b] no son combinaciones válidas. Para simplificar, vamos a mantenerlo en dos elementos por combinación. Por lo tanto, la salida sería una matriz 2D NumPy con 2 columnas.

El resultado deseado sería esencialmente el mismo que el producto itertools.product , excepto que necesitamos enmascarar las combinaciones que se repiten. Como tal, podemos resolverlo para un caso de muestra, como así:

 In [510]: import numpy as np In [511]: a = np.array([4,2,9,1,3]) In [512]: from itertools import product In [513]: np.array(list(product(a,repeat=2)))[~np.eye(len(a),dtype=bool).ravel()] Out[513]: array([[4, 2], [4, 9], [4, 1], [4, 3], [2, 4], [2, 9], [2, 1], [2, 3], [9, 4], [9, 2], [9, 1], [9, 3], [1, 4], [1, 2], [1, 9], [1, 3], [3, 4], [3, 2], [3, 9], [3, 1]]) 

Pero crear ese enorme conjunto y luego ocultarlo y, por lo tanto, no usar algunos elementos, no me parece demasiado eficiente.

Eso me hizo pensar si se podría aprovechar numpy.ndarray.strides aquí. Tengo una solución con esa idea en mente, la cual publicaré como una respuesta, pero me encantaría ver otras más eficientes.

En términos de uso: nos encontramos con estos casos con matrices de adyacencia, entre otras, y pensé que sería bueno resolver este problema. Para un plug-n-play más fácil y eficiente en otros problemas, sería bueno tener la salida final que no sea una vista de alguna matriz intermedia.

Parece que np.lib.stride_tricks.as_strided podría usarse para maximizar la eficiencia de las views y np.lib.stride_tricks.as_strided la copia hasta la etapa final, donde asignamos a una matriz inicializada. La implementación se realizaría en dos pasos, con algunos trabajos necesarios para la segunda columna (como se muestra en el caso de muestra en la pregunta), que estamos llamando como one-cold (nombre de fantasía que denota un elemento que falta por secuencia / está frío en a cada intervalo de len(input_array) - 1 )

 def onecold(a): n = len(a) s = a.strides[0] strided = np.lib.stride_tricks.as_strided b = np.concatenate((a,a[:-1])) return strided(b[1:], shape=(n-1,n), strides=(s,s)) 

Para mostrar, una onecold con un caso de muestra –

 In [563]: a Out[563]: array([4, 2, 9, 1, 3]) In [564]: onecold(a).reshape(len(a),-1) Out[564]: array([[2, 9, 1, 3], [4, 9, 1, 3], [4, 2, 1, 3], [4, 2, 9, 3], [4, 2, 9, 1]]) 

Para resolver el problema original, lo usaremos como tal –

 def combinations_without_repeat(a): n = len(a) out = np.empty((n,n-1,2),dtype=a.dtype) out[:,:,0] = np.broadcast_to(a[:,None], (n, n-1)) out.shape = (n-1,n,2) out[:,:,1] = onecold(a) out.shape = (-1,2) return out 

Ejecución de la muestra

 In [574]: a Out[574]: array([4, 2, 9, 1, 3]) In [575]: combinations_without_repeat(a) Out[575]: array([[4, 2], [4, 9], [4, 1], [4, 3], [2, 4], [2, 9], [2, 1], [2, 3], [9, 4], [9, 2], [9, 1], [9, 3], [1, 4], [1, 2], [1, 9], [1, 3], [3, 4], [3, 2], [3, 9], [3, 1]]) 

Parece bastante eficiente para una matriz de 1000 elementos de ints

 In [578]: a = np.random.randint(0,9,(1000)) In [579]: %timeit combinations_without_repeat(a) 100 loops, best of 3: 2.35 ms per loop 

Me encantaría ver a los demás!

“Sería esencialmente igual a la salida de itertools.product , esperar que necesitemos enmascarar las combinaciones que se repiten”. En realidad, lo que quieres es itertools.permutations :

 In [7]: import numpy as np In [8]: from itertools import permutations In [9]: a = np.array([4,2,9,1,3]) In [10]: list(permutations(a, 2)) Out[10]: [(4, 2), (4, 9), (4, 1), (4, 3), (2, 4), (2, 9), (2, 1), (2, 3), (9, 4), (9, 2), (9, 1), (9, 3), (1, 4), (1, 2), (1, 9), (1, 3), (3, 4), (3, 2), (3, 9), (3, 1)] 

Evaluación comparativa

Publicando los números / cifras de rendimiento para los enfoques propuestos hasta ahora en esta publicación wiki.

Configuración del sistema:

 NumPy version : 1.13.3 Python version : 2.7.12 (GCC 5.4.0) Operating System: Ubuntu 16.04 RAM: 16GB CPU Model: Intel(R) Core(TM) i7-6700HQ CPU @ 2.60GHz (# Cores=4, # Threads=8) 

La configuración de benchmarking sería:

 import numpy as np import perfplot from itertools import permutations # https://stackoverflow.com/a/48234170/ @Divakar def onecold(a): n = len(a) s = a.strides[0] strided = np.lib.stride_tricks.as_strided b = np.concatenate((a,a[:-1])) return strided(b[1:], shape=(n-1,n), strides=(s,s)) # https://stackoverflow.com/a/48234170/ @Divakar def combinations_without_repeat(a): n = len(a) out = np.empty((n,n-1,2),dtype=a.dtype) out[:,:,0] = np.broadcast_to(a[:,None], (n, n-1)) out.shape = (n-1,n,2) out[:,:,1] = onecold(a) out.shape = (-1,2) return out # https://stackoverflow.com/a/48234349/ @Warren Weckesser def itertools_permutations(a): return np.array(list(permutations(a, 2))) perfplot.show( setup=lambda n: np.random.rand(n), n_range=[10,20,50,100,200,500,1000], # dataset sizes kernels=[combinations_without_repeat, itertools_permutations], logx=True, logy=True, ) 

La cifra de rendimiento:

introduzca la descripción de la imagen aquí