Iterando sobre múltiples índices con i> j (> k) de forma pythonica

Necesito iterar sobre una tupla de índices. todos los índices deben estar en el rango [0, N) con la condición i > j . El ejemplo de juguete que presento aquí trata solo con dos índices; Necesitaré extender eso a tres (con i > j > k ) o más.

La versión básica es esta:

 N = 5 for i in range(N): for j in range(i): print(i, j) 

Y funciona bien; la salida es

 1 0 2 0 2 1 3 0 3 1 3 2 4 0 4 1 4 2 4 3 

No quiero tener un nivel de sangría más para cada índice adicional, por lo tanto, prefiero esta versión:

 for i, j in ((i, j) for i in range(N) for j in range(i)): print(i, j) 

esto funciona perfectamente bien, hace lo que debería y elimina el nivel de sangrado adicional.

Esperaba poder tener algo más elegante (para dos índices que no es tan relevante, pero para tres o más se vuelve más relevante). Lo que se me ocurrió hasta ahora es esto:

 from itertools import combinations for j, i in combinations(range(N), 2): print(i, j) 

Esto itera sobre el mismo par de índices muy bien. Lo único que es diferente es el orden en que aparecen los pares:

 1 0 2 0 3 0 4 0 2 1 3 1 4 1 3 2 4 2 4 3 

Como el orden de lo que estoy haciendo con estos índices es relevante, por lo tanto no puedo usar esto.

¿Existe una forma elegante, corta y pythonica de iterar sobre estos índices en el mismo orden que produce el primer ejemplo? Tenga en cuenta que N será grande, por lo que la clasificación no es algo que me gustaría hacer.

Podrías resolver esto generalmente como sigue:

 def indices(N, length=1): """Generate [length]-tuples of indices. Each tuple t = (i, j, ..., [x]) satisfies the conditions len(t) == length, 0 <= i < N and i > j > ... > [x]. Arguments: N (int): The limit of the first index in each tuple. length (int, optional): The length of each tuple (defaults to 1). Yields: tuple: The next tuple of indices. """ if length == 1: for x in range(N): yield (x,) else: for x in range(1, N): for t in indices(x, length - 1): yield (x,) + t 

En uso:

 >>> list(indices(5, 2)) [(1, 0), (2, 0), (2, 1), (3, 0), (3, 1), (3, 2), (4, 0), (4, 1), (4, 2), (4, 3)] >>> list(indices(5, 3)) [(2, 1, 0), (3, 1, 0), (3, 2, 0), (3, 2, 1), (4, 1, 0), (4, 2, 0), (4, 2, 1), (4, 3, 0), (4, 3, 1), (4, 3, 2)] 

Aquí hay un enfoque con itertools.combinations para tener un número genérico de niveles :

 map(tuple,(N-1-np.array(list(combinations(range(N),M))))[::-1]) 

O un poco retorcido con el mismo método.

 map(tuple,np.array(list(combinations(range(N-1,-1,-1),M)))[::-1]) 

, donde N: número de elementos y M: número de niveles.

Ejecución de la muestra

 In [446]: N = 5 ...: for i in range(N): ...: for j in range(i): ...: for k in range(j): # Three levels here ...: print(i, j, k) ...: (2, 1, 0) (3, 1, 0) (3, 2, 0) (3, 2, 1) (4, 1, 0) (4, 2, 0) (4, 2, 1) (4, 3, 0) (4, 3, 1) (4, 3, 2) In [447]: N = 5; M = 3 In [448]: map(tuple,(N-1-np.array(list(combinations(range(N),M))))[::-1]) Out[448]: [(2, 1, 0), (3, 1, 0), (3, 2, 0), (3, 2, 1), (4, 1, 0), (4, 2, 0), (4, 2, 1), (4, 3, 0), (4, 3, 1), (4, 3, 2)] 

Puede usar el product de itertools si no le importa la ineficiencia de tirar la mayor parte de las tuplas generadas. (La ineficiencia empeora a medida que aumenta el parámetro de repeat ).

 >>> from itertools import product >>> for p in ((i,j) for (i,j) in product(range(5), repeat=2) if i > j): ... print p ... (1, 0) (2, 0) (2, 1) (3, 0) (3, 1) (3, 2) (4, 0) (4, 1) (4, 2) (4, 3) >>> for p in ((i,j,k) for (i,j,k) in product(range(5), repeat=3) if i > j > k): ... print p ... (2, 1, 0) (3, 1, 0) (3, 2, 0) (3, 2, 1) (4, 1, 0) (4, 2, 0) (4, 2, 1) (4, 3, 0) (4, 3, 1) (4, 3, 2) 

Actualización: en lugar de desempaquetar tuple, usando la indexación para el filtro. Esto permite que el código se escriba un poco más compacto. Solo my_filter necesario cambiar my_filter para tuplas de diferentes tamaños.

 from itertools import product, ifilter def my_filter(p): return p[0] > p[1] > p[2] for p in ifilter(my_filter, product(...)): print p 

Este es un enfoque basado en la observación de que es más fácil generar los negativos de los índices en el (orden inverso) del orden deseado. Es similar al enfoque de @Divakar y tiene el inconveniente de requerir que se cree la lista. en memoria:

 def decreasingTuples(N,k): for t in reversed(list(itertools.combinations(range(1-N,1),k))): yield tuple(-i for i in t) >>> for t in decreasingTuples(4,2): print(t) (1, 0) (2, 0) (2, 1) (3, 0) (3, 1) (3, 2) >>> for t in decreasingTuples(4,3): print(t) (2, 1, 0) (3, 1, 0) (3, 2, 0) (3, 2, 1) 

un bash un tanto ‘hacky’ usando eval (simplemente agregando esto para completar. ¡Hay respuestas más agradables aquí!).

la idea es construir una cadena como

 '((a, b, c) for a in range(5) for b in range(a) for c in range(b))' 

y devolver la eval de eso:

 def ijk_eval(n, depth): ''' construct a string representation of the genexpr and return eval of it... ''' var = string.ascii_lowercase assert len(var) >= depth > 1 # returns int and not tuple if depth=1 for_str = ('for {} in range({}) '.format(var[0], n) + ' '.join('for {} in range({})'.format(nxt, cur) for cur, nxt in zip(var[:depth-1], var[1:depth]))) return eval('(({}) {})'.format(', '.join(var[:depth]), for_str)) 

Se puede utilizar de esta manera y produce los resultados correctos.

 for i, j in ijk_eval(n=5, depth=2): print(i, j) 

La construcción no es muy agradable, pero el resultado es: es un genexpr regular y tan eficiente como esos.