代码之家 › 专栏 › 技术社区 › hiro protagonist

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

itertools python-3.x python

hiro protagonist · 技术社区 · 8 年前

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

基本版本如下:

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

它工作得很好;输出为:

我不想每增加一个索引就增加一个缩进级别, 因此,我更喜欢这个版本:

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)

这会在同一对索引上进行迭代。唯一的事情是不同的是成对出现的顺序:

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

是否有一种优雅、简短、python式的方法,可以按照第一个示例生成的相同顺序迭代这些索引?记住 N 会很大,所以排序不是我想做的事情。

5 回复 | 直到 8 年前

jonrsharpe A l w a y s S u n n y 8 年前

您通常可以通过以下方式解决此问题:

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

Divakar 8 年前

以下是一种方法: 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)]

chepner 8 年前

您可以使用 product 从…起 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

John Coleman 8 年前

这是一种基于观察的方法,即更容易生成底片在所需顺序(相反)的索引中,它类似于@Divakar的方法,类似的方法具有需要在内存中创建列表的缺点:

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)

-1

hiro protagonist 8 年前

使用 eval (只是为了完整起见添加了这个。这里有更好的答案!)。

其思想是构造一个字符串,如

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

并返回 评估 其中:

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

可以以这种方式使用,并产生正确的结果。

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

结构不是很好-但结果是:它是一个规则 genexpr 而且和那些一样有效。