Algorithm to find a filtered set of combinations

Question

I'm using Python to find a filtered set of combinations of pairs computed via a Cartesian product. I can calculate what I need using a heuristic algorithm but it feels clunky and I'm afraid I'm reinventing something that is probably a known and solved math concept for which better algorithms exist.

Here's a example:

Assume I have an order for 2 products, A and B, and I have inventory in 3 warehouses (1,2,3). I'd like to compute all possible ways I can ship this order, in total or in part, from one of my 3 warehouses. Assume unlimited inventory, so no constraints. The resulting list of possible ways will ultimately be fed into an optimization routine to minimize shipping costs etc. However, to start I'd like to find a more elegant (and likely more scalable) way to compute the list of possible fulfillment options.

Here's what I have so far. Any ideas on how this can be solved in more mathematically efficient way would be much appreciated. I'm not looking for ways to avoid the for loop, I know I can probably use broadcasting. Thanks!

from itertools import *

# Products in order
P = ['A', 'B'] 

# Possible warehouses
W = ['1', '2', '3'] 

# Get the Cartesian product of all products in the order
# and all warehouses
PW = list(product(P, W))

Result:

[('A', '1'), 
 ('A', '2'), 
 ('A', '3'), 
 ('B', '1'), 
 ('B', '2'), 
 ('B', '3')]

Then, compute the possible combinations of these product/warehouse pairs

pwc = list(combinations(PW, 2))

Result:

[(('A', '1'), ('A', '2')),
 (('A', '1'), ('A', '3')),
 (('A', '1'), ('B', '1')),
 (('A', '1'), ('B', '2')),
 (('A', '1'), ('B', '3')),
 (('A', '2'), ('A', '3')),
 (('A', '2'), ('B', '1')),
 (('A', '2'), ('B', '2')),
 (('A', '2'), ('B', '3')),
 (('A', '3'), ('B', '1')),
 (('A', '3'), ('B', '2')),
 (('A', '3'), ('B', '3')),
 (('B', '1'), ('B', '2')),
 (('B', '1'), ('B', '3')),
 (('B', '2'), ('B', '3'))]

Lastly, filter out any combinations where we would ship the same product from a different warehouses:

[u for u in pwc if ((u[0][0] != u[1][0]) and (u[0][1] != u[1][1]))]

Result:

[(('A', '1'), ('B', '2')),
 (('A', '1'), ('B', '3')),
 (('A', '2'), ('B', '1')),
 (('A', '2'), ('B', '3')),
 (('A', '3'), ('B', '1')),
 (('A', '3'), ('B', '2'))]

So, is there such a thing as a "filtered cartesian join combination"?

(Hope this all makes sense!)

Answer 1

As far as I can tell this one-liner solves your problem:

from itertools import permutations, repeat
[tuple(zip(x, y)) for x, y in zip(repeat('AB'), permutations('123', 2))]

Output:

[(('A', '1'), ('B', '2')),
 (('A', '1'), ('B', '3')),
 (('A', '2'), ('B', '1')),
 (('A', '2'), ('B', '3')),
 (('A', '3'), ('B', '1')),
 (('A', '3'), ('B', '2'))]

The difference between this and your method is that you generate all and then filter, while I found a pattern in your expected output and came up with this method.

If anyone can see a better way to simplify this, be welcome to suggest it.

Answer 2

Try this:

from itertools import *

# Products in order
P = ['A', 'B'] 

# Possible warehouses
W = ['1', '2', '3'] 

# Get the Cartesian product of all products in the order
# and all warehouses
PW = list(product(P, W))

# Split PW in two groups based on P then product those groups
u = list(product(*[list(filter(lambda x: x[0] == i, PW)) for i in P]))

# Filter result for where different W's
list(filter(lambda x: x[0][1] != x[1][1], u))

Output:

[(('A', '1'), ('B', '2')),
 (('A', '1'), ('B', '3')),
 (('A', '2'), ('B', '1')),
 (('A', '2'), ('B', '3')),
 (('A', '3'), ('B', '1')),
 (('A', '3'), ('B', '2'))]