python - tuplas - Iteración sobre múltiples índices con i> j(> k) de forma pitónica

llenar una lista en python

Question

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; Tendré que 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 por 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, hace lo que debe y se deshace del nivel de indentación adicional.

Tenía la esperanza de 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 manera elegante, breve y pitónica de iterar sobre estos índices en el mismo orden que el primer ejemplo? Tenga en cuenta que N será grande, por lo que clasificar no es algo que quisiera hacer.

Answer 1

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

Answer 2

Este es un enfoque basado en la observación de que es más fácil generar los negativos de los índices en (el reverso de) el 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)

Answer 3

Usted podría resolver esto generalmente de la siguiente manera:

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

Answer 4

Puede utilizar el product de itertools si no le importa la ineficiencia de descartar la mayoría 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 tuplas, usar indexación para el filtro. Esto permite que el código se escriba un poco más compacto. Solo se debe cambiar my_filter por 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

Answer 5

un intento un tanto ''hacky'' de usar eval (simplemente agregando esto para completar, ¡aquí hay respuestas más agradables!).

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 devuelve 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 usar 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 buena, pero el resultado es: es un genexpr regular y tan eficiente como esos.