avoid computing whole cartesian product (python itertools)

Question

My goal is to find any permutation of a diagonal in a nxn matrix (2 <= n <= 15). The matrix consists of zeros and ones.

Currently I do it like this:

  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

This works fine if the matrix is not too large, but otherwise it fails with: MemoryError

So is there a way to avoid the whole computation of cart? so that it for example one permutation is found, the computation stops?

You are creating multiple copies for no reason. Remove the list call on itertools.product(*indices) and the cart = [list(tup) for tup in cart] is also unnecessary. Also the filter would be slower than just doing it using a list comp. — Padraic Cunningham
– Padraic Cunningham, Commented Nov 4, 2016 at 15:02
Why are you doing list(itertools.product(*indices))? You may easily filter data lazily. Can you add information on Python version used? Python 2.x and 3.x would be slightly different here. — Łukasz Rogalski
– Łukasz Rogalski, Commented Nov 4, 2016 at 15:03
I'm using python 2.7. how can I filter it lazily? Since I have a list of indices per row, I want to select one index per item, how else can this be done without itertools.product ? — ph0t3k
– ph0t3k, Commented Nov 4, 2016 at 15:04
cart = [p for p in itertools.product(*indices) if len(set(p)) == len(p)] — Padraic Cunningham
– Padraic Cunningham, Commented Nov 4, 2016 at 15:09

Moses Koledoye · Accepted Answer · 2016-11-04 15:05:07Z

1

Simply make all the evaluations lazy by not calling list on the result of itertools.product and using itertools.ifilter in place of 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 returns the first case where the predicate in ifilter is True or returns None in case there is no matching item.

The computation stops once a matching item is found.

answered Nov 4, 2016 at 15:05

Moses Koledoye

78.8k8 gold badges139 silver badges141 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

John Zwinck · Accepted Answer · 2016-11-04 15:11:45Z

0

You can simplify the last part of your code to have it just return the first answer:

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

In other words, don't be so clever with filter and lambda and all that--it's unnecessary.

answered Nov 4, 2016 at 15:11

John Zwinck

252k44 gold badges346 silver badges459 bronze badges

2 Comments

ph0t3k Over a year ago

Hehe yes, I'm kind of trying to use list comprehension and lambda expressions all the time, but I also think its nicer to read than for loops.

John Zwinck Over a year ago

@ph0t3k: Most people would find the for-if in my answer to be a lot easier to read than next(ifilter(lambda.... Think of future maintainers of your code.

Collectives™ on Stack Overflow

avoid computing whole cartesian product (python itertools)

2 Answers 2

Comments

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related