Python itertools.product переупорядочить поколение

Question

У меня есть это:

shape = (2, 4) # arbitrary, could be 3 dimensions such as (3, 5, 7), etc...

for i in itertools.product(*(range(x) for x in shape)):
    print(i)

# output: (0, 0) (0, 1) (0, 2) (0, 3) (1, 0) (1, 1) (1, 2) (1, 3)

Пока все хорошо, itertools.product продвигает самый правый элемент на каждой итерации.Но теперь я хочу иметь возможность указать порядок итераций в соответствии со следующим:

axes = (0, 1) # normal order
# output: (0, 0) (0, 1) (0, 2) (0, 3) (1, 0) (1, 1) (1, 2) (1, 3)

axes = (1, 0) # reversed order
# output: (0, 0) (1, 0) (2, 0) (3, 0) (0, 1) (1, 1) (2, 1) (3, 1)

Если бы shapes имел три измерения, axes мог бы быть, например, (0, 1, 2) или (2, 0, 1) и т. Д.так что это не просто использование reversed().Итак, я написал некоторый код, который делает это, но кажется очень неэффективным:

axes = (1, 0)

# transposed axes
tpaxes = [0]*len(axes)
for i in range(len(axes)):
    tpaxes[axes[i]] = i

for i in itertools.product(*(range(x) for x in shape)):
    # reorder the output of itertools.product
    x = (i[y] for y in tpaxes)
    print(tuple(x))

Есть идеи, как правильно это сделать?

Answer 1

Ну, на самом деле это специализированное руководство product.Это должно быть быстрее, так как оси переупорядочиваются только один раз:

def gen_chain(dest, size, idx, parent):
    # iterate over the axis once
    # then trigger the previous dimension to update
    # until everything is exhausted
    while True:
        if parent: next(parent) # StopIterator is propagated upwards

        for i in xrange(size):
            dest[idx] = i
            yield 

        if not parent: break

def prod(shape, axes):
    buf = [0] * len(shape)
    gen = None

    # EDIT: fixed the axes order to be compliant with the example in OP 
    for s, a in zip(shape, axes):
        # iterate over the axis and put to transposed
        gen = gen_chain(buf, s, a, gen)

    for _ in gen:
        yield tuple(buf)


print list(prod((2,4), (0,1)))
# [(0, 0), (0, 1), (0, 2), (0, 3), (1, 0), (1, 1), (1, 2), (1, 3)]
print list(prod((2,4), (1,0)))
# [(0, 0), (1, 0), (2, 0), (3, 0), (0, 1), (1, 1), (2, 1), (3, 1)]
print list(prod((4,3,2),(1,2,0)))
# [(0, 0, 0), (1, 0, 0), (0, 0, 1), (1, 0, 1), (0, 0, 2), (1, 0, 2), ...

Answer 2

Если вы можете себе это позволить в памяти: позвольте itertools.product выполнить тяжелую работу и используйте zip для переключения осей.

import itertools
def product(shape, axes):
    prod_trans = tuple(zip(*itertools.product(*(range(shape[axis]) for axis in axes))))

    prod_trans_ordered = [None] * len(axes)
    for i, axis in enumerate(axes):
        prod_trans_ordered[axis] = prod_trans[i]
    return zip(*prod_trans_ordered)

Маленький тест:

>>> print(*product((2, 2, 4), (1, 2, 0)))
(0, 0, 0) (1, 0, 0) (0, 0, 1) (1, 0, 1) (0, 0, 2) (1, 0, 2) (0, 0, 3) (1, 0, 3) (0, 1, 0) (1, 1, 0) (0, 1, 1) (1, 1, 1) (0, 1, 2) (1, 1, 2) (0, 1, 3) (1, 1, 3)

Приведенная выше версия работает быстро, если не слишком много продуктов. Для больших наборов результатов следующее выполняется быстрее, но ... использует eval (хотя и довольно безопасным способом):

def product(shape, axes):
    d = dict(("r%i" % axis, range(shape[axis])) for axis in axes)
    text_tuple = "".join("x%i, " % i for i in range(len(axes)))
    text_for = " ".join("for x%i in r%i" % (axis, axis) for axis in axes)
    return eval("((%s) %s)" % (text_tuple, text_for), d)

Редактировать: Если вы хотите изменить не только порядок итераций, но и форму (как в примере с OP), необходимы небольшие изменения:

import itertools
def product(shape, axes):
    prod_trans = tuple(zip(*itertools.product(*(range(s) for s in shape))))

    prod_trans_ordered = [None] * len(axes)
    for i, axis in enumerate(axes):
        prod_trans_ordered[axis] = prod_trans[i]
    return zip(*prod_trans_ordered)

И eval версия:

def product(shape, axes):
    d = dict(("r%i" % axis, range(s)) for axis, s in zip(axes, shape))
    text_tuple = "".join("x%i, " % i for i in range(len(axes)))
    text_for = " ".join("for x%i in r%i" % (axis, axis) for axis in axes)
    return eval("((%s) %s)" % (text_tuple, text_for), d)

Тест:

>>> print(*product((2, 2, 4), (1, 2, 0)))
(0, 0, 0) (1, 0, 0) (2, 0, 0) (3, 0, 0) (0, 0, 1) (1, 0, 1) (2, 0, 1) (3, 0, 1) (0, 1, 0) (1, 1, 0) (2, 1, 0) (3, 1, 0) (0, 1, 1) (1, 1, 1) (2, 1, 1) (3, 1, 1)

Answer 3

Вы пробовали время, чтобы увидеть, сколько времени это займет?То, что у вас есть, не должно быть намного медленнее, чем без переупорядочения.

Вы можете попробовать изменить то, что вам нужно, для использования сращивания на месте.

tpaxes = tuple(tpaxes)
for i in itertools.product(*(range(x) for x in shape)):
    # reorder the output of itertools.product
    i[:] = (i[y] for y in tpaxes)
    print(tuple(x))

Также вы можете получить ускорение с помощьюпревращение tpaxes в локальную переменную функции, а не в глобальную переменную (время поиска которой медленнее)

В противном случае я предлагаю написать свою собственную функцию продукта ..

Answer 4

Я не знаю, насколько это эффективно, но вы должны быть в состоянии сделать что-то подобное ...

shape = (2, 4, 3)
axes = (2, 0, 1)

# Needed to get the original ordering back
axes_undo = tuple(reversed(axes))

# Reorder the shape in a configuration so that .product will give you
# the order you want.
reordered = tuple(reversed(map(lambda x: shape[x], list(axes))))

# When printing out the results from .product, put the results back
# into the original order.
for i in itertools.product(*(range(x) for x in reordered)):
    print(tuple(map(lambda x: i[x], list(axes_undo))))

Я пробовал до 4-х измерений, и, кажется, работает. ;)

Я просто поменяю размеры вокруг, а затем верну их обратно.

Answer 5

import itertools

normal = (0, 1)
reverse = (1, 0)

def axes_ordering(x):
    a, b = x
    return b - a

shape = (2, 4)

for each in itertools.product(*(range(x) for x in shape)):
    print(each[::axes_ordering(normal)], each[::axes_ordering(reverse)])

результат:

(0, 0) (0, 0)
(0, 1) (1, 0)
(0, 2) (2, 0)
(0, 3) (3, 0)
(1, 0) (0, 1)
(1, 1) (1, 1)
(1, 2) (2, 1)
(1, 3) (3, 1)

Answer 6

for i in itertools.product(*(range(x) for x in reversed(shape))):
    print tuple(reversed(i))