I need to output cartesian product of N lists in specific order.
I know how to build products in "default" order:
Given sets (a, b, c), (x, y), (1, 2, 3)
, first I produce ax1
, then iterate over last set to get ax2
, ax3
, then change element in the second set and iterate over the last set again for ay1
, ay2
, ay3
, etc...
The order I need should not go for the N
-th element in any set, before producing products of N-1
elements
Desired result is ax1, ax2, ay1, ay2, bx1, bx2, by1, by2, ax3, ay3, bx3, by3, cx1, cx2, cx3, cy1, cy2, cy3
. See, I don't get ax3
(containing 3rd element from (1, 2, 3)
), before producing all products with 2nd elements.
My current algorithm is:
- trunace sets to length
1
- generate products
- truncate sets to length
2
- generate products
- remove duplicates, preserving order
- ...
- truncate sets to length
max length of all sets
- generate products
- remove duplicates, preserving order
Each step "generate products" also generates all products from the previous step, so I have to remove them
Is it the better algorith to get desired order? Does it have a name?
CodePudding user response:
Not sure if this order has a name, but this seems to do what you ask for without having to remove repeated items.
from itertools import islice, product, zip_longest
def specific_order_cartesian(lists):
its = [[lst[0]] for lst in lists]
yield tuple(lst[0] for lst in lists)
for column in list(islice(zip_longest(*lists), 1, None)):
for i, p in reversed(list(enumerate(column))):
if p is None:
continue
yield from product(
*(
(p,) if j == i else its[j]
for j in range(len(lists))
)
)
its[i].append(p)
print(list(specific_order_cartesian(
[('a', 'b', 'c',), ('x', 'y'), (1, 2, 3)]
)))