Geek Answers Handbook

Iterating over itertools.product in a different order without creating a list

I have iterability that covers a huge search space. My plan is not to complete the script, but just kill it after a certain time.

Now I need a Cartesian product of this space and a search there. itertools.product produces this order:

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

For now, I want to do a search in diagonal order like:

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

sorted with some key function that returns the sum of the elements of a tuple would be my regular approach, but to sort all the data should be checked, which is not possible in my case. Is there any way to do this?

This question is very similar to this , but there sorted is still used in the answer. Also I do not see how to adapt ordered_combinations to ordered_product .

+6
source share
2 answers

The question is equivalent to asking how to create all n-tuples with a given sum for sequential and increasing values ​​of the sum:

  (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

For any given row (with a given target sum), the subtask is equivalent to the dynamic programming task Number of ways to make changes for the sum N or Number of ways to sum the sum S with N numbers .

Also see entries in Combinatorial Algorithms by Donald Knuth.

0
source

It’s actually quite simple to calculate the indices for the diagonals for the case 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[ij], inp[j] # lower right triangle for i in range(1, n): for j in range(ni): yield inp[nj-1], inp[i+j]

Just to show the results:

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

The function itself may be a little more complicated (or slower) than it should be, but so far I have not been able to find any reference implementation for this case.

If you enter range you can also avoid all indexing and just return the indexes:

 def diagonal_product(n): # upper left triangle for i in range(n): for j in range(i+1): yield ij, j # lower right triangle for i in range(1, n): for j in range(ni): yield nj-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)]
0
source

More articles:


All Articles