избежать вычисления всего декартова продукта (python itertools)

Question

Моя цель - найти любую перестановку диагонали в матрице nxn (2 < = n < = 15). Матрица состоит из нулей и единиц.

В настоящее время я делаю это так:

indices = [[j for j, x in enumerate(row) if x == 1] 
       for row in self.matrix] 
    cart = list(itertools.product(*indices)) 
    cart = [list(tup) for tup in cart] 
    cart = filter(lambda dia: len(list(set(dia))) == len(dia), cart) 
    return cart 

Это прекрасно работает, если матрица не слишком велика, но в остальном он терпит неудачу с: MemoryError

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

Answer 1

Просто сделайте все оценки ленивы, не называя list на результате itertools.product и использования itertools.ifilter вместо filter:

from itertools import ifilter, product 

indices = [[j for j, x in enumerate(row) if x == 1] for row in self.matrix] 
cart = product(*indices) 
found_cart = next(ifilter(lambda dia: len(set(dia)) == len(dia), cart), None) 

next возвращает первый случай, когда предикат ifilter является True или возвращает None в кейс нет соответствующий товар.

Расчет останавливается после того, как найден соответствующий элемент.

Answer 2

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

def foo(matrix): 
    indices = [[j for j, x in enumerate(row) if x == 1] for row in matrix] 

    # this part is changed, very simple and efficient now 
    for dia in itertools.product(*indices): 
     if len(set(dia)) == len(dia): 
      return dia 

Другими словами, не будь такой умный с filter и лямбда, и все, что - это лишнее ,