以pythonic方式迭代i> j(> k)的多个索引

Question

我需要迭代一个索引元组.所有指数必须在[0, N)条件范围内 i > j.我在这里介绍的玩具示例只涉及两个指数; 我需要将其扩展到三个(有i > j > k)或更多.

基本版本是这样的:

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

它工作得很好; 输出是

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

我不希望每个附加索引都有一个缩进级别,因此我更喜欢这个版本:

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

这非常有效,它应该做什么,并摆脱额外的缩进水平.

我希望能够有更优雅的东西(两个指数并非完全相关,但三个或更多指数变得更相关).到目前为止我想出的是:

from itertools import combinations

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

这很好地迭代了同一对索引.唯一不同的是对出现的顺序:

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

由于我对这些指数的处理顺序是相关的,因此我不能使用它.

是否有一种优雅,简短,pythonic的方式来迭代这些索引的顺序与第一个例子产生的顺序相同？请记住,这N将是很大的,所以排序不是我想要做的事情.

Answer 1

你可以解决这个问题,如下所示:

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

正在使用:

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

你可以使用productfrom,itertools如果你不介意丢弃大多数生成的元组的效率低下.(随着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)

更新:使用索引进行过滤,而不是元组解包.这允许代码更紧凑地编写.只my_filter需要针对不同大小的元组进行更改.

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 3

这是一种itertools.combinations具有通用数量级别的方法 -

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

或者用同样的方法扭曲一下 -

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

,其中N:元素数量和M:级别数量.

样品运行 -

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