Iterating Over Multiple Indices With I > J ( > K) In A Pythonic Way

i need to iterate over a tuple of indices. all indices must be in the range [0, N) with the condition i > j. The toy example I present here deals with only two indices; I will n

Solution 1:

You could solve this generally as follows:

defindices(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 inrange(N):
           yield (x,)
    else:
       for x inrange(1, N):
            for t in indices(x, length - 1):
                yield (x,) + t

In use:

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

Solution 2:

Here's an approach with itertools.combinations to have a generic number of levels -

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

Or a bit twisted one with same method -

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

, where N : number of elements and M : number of levels.

Sample run -

In [446]: N = 5
     ...: for i inrange(N):
     ...:     for j inrange(i):
     ...:         for k inrange(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)]

Solution 3:

You can use product from itertools if you don't mind the inefficiency of throwing out most of the generated tuples. (The inefficiency gets worse as the repeat parameter increases.)

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

---

Update: Instead of tuple unpacking, using indexing for the filter. This allows the code to be written a little more compactly. Only my_filter needs to be changed for tuples of varying sizes.

fromitertoolsimportproduct, ifilterdefmy_filter(p):
    returnp[0] > p[1] > p[2]forpinifilter(my_filter, product(...)):
    printp

Solution 4:

This is an approach based on the observation that it is easier to generate the negatives of the indices in the (reverse of) the desired order It is similar to the approach of @Divakar and like that has the drawback of requiring the list to be created in memory:

defdecreasingTuples(N,k):
    for t inreversed(list(itertools.combinations(range(1-N,1),k))):
        yieldtuple(-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)

Solution 5:

a somewhat 'hacky' attempt using eval (just adding this for completeness. there are nicer answers here!).

the idea is to construct a string like

'((a, b, c) forainrange(5) forbinrange(a) forcinrange(b))'

and return the eval of that:

defijk_eval(n, depth):
    '''
    construct a string representation of the genexpr and return eval of it...
    '''

    var = string.ascii_lowercase
    assertlen(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 inzip(var[:depth-1], var[1:depth])))
    returneval('(({}) {})'.format(', '.join(var[:depth]), for_str))

can be used this way and produces the right results.

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

the construction is not very nice - but the result is: it is a regular genexpr and just as efficient as those are.