python - 查找一组经过过滤的组合的算法

Question

我正在使用 Python 来查找通过笛卡尔积计算的一组经过过滤的对组合。我可以使用启发式算法计算我需要的东西，但感觉很笨拙，而且我担心我正在重新发明一些可能是已知且已解决的数学概念的东西，而存在更好的算法。

这是一个例子:

假设我有 2 个产品 A 和 B 的订单，并且我在 3 仓库 (1,2,3) 中有库存。我想计算从我的 3 个仓库之一全部或部分运送此订单的所有可能方式。假设库存无限，因此没有限制。可能的方法的结果列表最终将被输入到优化例程中，以最大限度地减少运输成本等。但是，首先我想找到一种更优雅(并且可能更具可扩展性)的方法来计算可能的履行选项列表。

这是我到目前为止所拥有的。任何关于如何以更数学有效的方式解决这个问题的想法将不胜感激。我不是在寻找避免 for 循环的方法，我知道我可能可以使用广播。谢谢!

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

结果:

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

然后，计算这些产品/仓库对的可能组合

pwc = list(combinations(PW, 2))

结果:

[(('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'))]

最后，过滤掉我们从不同仓库运送相同产品的任何组合:

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

结果:

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

那么，是否存在“过滤笛卡尔连接组合”这样的东西？

(希望这一切都有意义!)

Answer 1

据我所知，这句话解决了您的问题:

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

输出:

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

此方法与您的方法之间的区别在于您生成所有内容然后进行过滤，而我在您的预期输出中发现了一种模式并提出了此方法。

如果有人能找到更好的方法来简化此操作，欢迎提出建议。