根据python中的条件创建值列表

Question

我需要创建一个作业列表，该列表尊重由字典声明的优先关系。

dict_preced = {(1, 2): 0,  (1, 3): 0,  (2, 1): 1,  (2, 3): 0,  (3, 1): 1,  (3, 2): 0}
Where (j1, j2) == 1 means that j1 requires j2, 0 otherwise.

假设我已经有了起始列表:j_seq = [3, 2, 1]，我需要创建一个new_list，其中所有来自j_seq的值都将尊重优先关系，这意味着在所需的作业之前没有作业正在执行。(即作业3和作业2不能在作业1之前执行)。

因此，存在多个候选列表(即new_list = [1, 2, 3]或new_list = [1, 3, 2])。如何创建new_list的样本，将始终尊重这些优先关系?

我发现了许多列表推导的例子，当每个值需要尊重给定的条件而不依赖于其他值时。但是，我没有发现任何例子中所述的条件涉及同一列表的两个值。

编辑:我不需要得到所有关于优先级约束的排列，只要一个就足够了。

Answer 1

一种解决方案是枚举j_seq的所有排列，然后根据您的优先级字典查找每个对组合，以识别无效且可能被丢弃的排列。

例如:

import itertools
dict_preced = {(1, 2): 0,  (1, 3): 0,  (2, 1): 1,  (2, 3): 0,  (3, 1): 1,  (3, 2): 0}
j_seq = [3, 2, 1]
valid = []
for perm in itertools.permutations(j_seq):
print('Permutation:', perm)
for perm_pair in itertools.combinations(perm, 2):
precedence = dict_preced.get(perm_pair, 0)
print('tCombination:', perm_pair, '=>', precedence)
if precedence == 1:
print('tDecision: exclude', perm)
break
else:
print('tDecision: include', perm)
valid.append(perm)
print('Result:', valid)

结果是:[(1, 3, 2), (1, 2, 3)].

完整的输出(包括调试日志)如下:

Permutation: (3, 2, 1)
Combination: (3, 2) => 0
Combination: (3, 1) => 1
Decision: exclude (3, 2, 1)
Permutation: (3, 1, 2)
Combination: (3, 1) => 1
Decision: exclude (3, 1, 2)
Permutation: (2, 3, 1)
Combination: (2, 3) => 0
Combination: (2, 1) => 1
Decision: exclude (2, 3, 1)
Permutation: (2, 1, 3)
Combination: (2, 1) => 1
Decision: exclude (2, 1, 3)
Permutation: (1, 3, 2)
Combination: (1, 3) => 0
Combination: (1, 2) => 0
Combination: (3, 2) => 0
Decision: include (1, 3, 2)
Permutation: (1, 2, 3)
Combination: (1, 2) => 0
Combination: (1, 3) => 0
Combination: (2, 3) => 0
Decision: include (1, 2, 3)
Result: [(1, 3, 2), (1, 2, 3)]

Answer 2

我在回答我自己的问题，因为我找到了解决这个问题的方法。

当使用短长度列表时，@jarmod提出的方法非常方便。然而，当考虑长列表时，使用他的方法变得不切实际，因为排列的数量增加到10^18。

对于那些可以从IBM CPLEX(或其他约束规划求解器)访问CP优化器的人来说，一个可能的替代方法是使用约束传播方法来获得一些有效序列的列表(尊重优先约束)。

在我的例子中，我通过docplex模块调用CP优化器。您可以在这里查看脚本:https://github.com/campioni1/CPO_Docplex_precedence_constraints

如果你遇到任何困难，请告诉我，