Iterate over itertools.product в другом порядке, никогда не создавая список

Question

У меня есть iterable, который покрывает огромное пространство для поиска. Мой план заключается не в том, чтобы сценарий завершился, а просто убил его через определенное время.

Теперь мне нужно декартово произведение этого пространства и поиск там. itertools.product производит этот заказ:

>>> list(itertools.product(range(3), repeat=2)) 
[(0, 0), (0, 1), (0, 2), (1, 0), (1, 1), (1, 2), (2, 0), (2, 1), (2, 2)] 

В то время как я хочу, чтобы искать в диагональном порядке, аналогичном:

[(0, 0), (0, 1), (1, 0), (0, 2), (1, 1), (2, 0), (1, 2), (2, 1), (2, 2)] 

sorted с некоторой ключевой функцией, которая возвращает сумму элементов кортежа будет моим регулярным но для сортировки все данные должны быть проверены, что в моем случае недопустимо. Есть ли способ сделать это?

Этот вопрос очень похож на this one, но там sorted по-прежнему используется в ответе. Также я не сразу вижу, как адаптировать ordered_combinations к ordered_product.

Answer 1

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

    (0, 0),    sum == 0 
       (0, 1), (1, 0),   sum == 1 
     (0, 2), (1, 1), (2, 0),   sum == 2 
      (1, 2), (2, 1),   sum == 3 
        (2, 2)    sum == 4 

Для любой данной строки (с заданной целевой суммой), подзадача эквивалентна задаче динамического программирования Number of ways to make change for amount N или Number of ways to add up to a sum S with N numbers.

Также см. Записи в Combinatorial Algorithms Дональдом Кнутом.

Answer 2

Это на самом деле довольно легко вычислить индексы для диагоналей для repeat=2 случая:

def diagonal_product(inp): 
    inp = tuple(inp) 
    n = len(inp) 
    # upper left triangle 
    for i in range(n): 
     for j in range(i+1): 
      yield inp[i-j], inp[j] 
    # lower right triangle 
    for i in range(1, n): 
     for j in range(n-i): 
      yield inp[n-j-1], inp[i+j] 

Просто, чтобы показать результаты:

>>> list(diagonal_product(range(4))) 
[(0, 0), (1, 0), (0, 1), (2, 0), (1, 1), (0, 2), (3, 0), (2, 1), (1, 2), 
(0, 3), (3, 1), (2, 2), (1, 3), (3, 2), (2, 3), (3, 3)] 

>>> list(diagonal_product(range(3))) 
[(0, 0), (1, 0), (0, 1), (2, 0), (1, 1), (0, 2), (2, 1), (1, 2), (2, 2)] 

Сама функция может быть немного сложнее (или медленнее), чем это должно быть, но я пока не нашел никакой ссылочной реализации для этого случая.

В случае range в качестве входных данных можно также избежать всех индексаций и просто вернуть показатели:

def diagonal_product(n): 
    # upper left triangle 
    for i in range(n): 
     for j in range(i+1): 
      yield i-j, j 
    # lower right triangle 
    for i in range(1, n): 
     for j in range(n-i): 
      yield n-j-1, i+j 

list(diagonal_product(3)) 
# [(0, 0), (1, 0), (0, 1), (2, 0), (1, 1), (0, 2), (2, 1), (1, 2), (2, 2)]