基于条件的快速匹配元组
|
我正在寻找以下问题的快速算法。
规则由有关元组的子句的组合表示。子句指定两个元组项目之间的关系。例如，“ 0”表示：“ 1”。
因此，规则可能是：
T(1)[2] = T(3)[1] AND T(1)[1] > T(2)[1]
(T(j)[i] op T(k)[l])
Clause (AND Clause)*
=
!=
>
<
<=
>=
(i11 i12 ... i1n)
...
(ik1 ik2 ... ikm)
T(1)[1] = T(2)[1] AND T(1)[3]>T(3)[1]
`(1 2 3 4)` T1
`(3 2 4)\' T2
`(4)` T3
`(1 5 3 6 7)` T4
T(1): T1, T(2): T4, T(3): T2
T(1): T4, T(2): T1, T(3): T2
没有找到相关结果
已邀请:
3 个回复
戒黑恳农
个排列（其中是元组的数量），可能满足约束条件（在最坏的情况下），因此您需要列出它们，因此的上限很严格。断跑胺弄萎
缔恃钨
模块的包装器。这是您问题中示例的解决方案：#!/usr/bin/env python from constraint import AllDifferentConstraint, Problem number_of_variables = 3 variables = [\"T(%d)\" % i for i in range(1, number_of_variables+1)] possible_values = [(1, 2, 3, 4), (3, 2, 4), (4,), (1, 5, 3, 6, 7)] problem = Problem() problem.addVariables(variables, possible_values) # each tuple should occur only once in the solution problem.addConstraint(AllDifferentConstraint(), variables) # T(1)[1] = T(2)[1] rule problem.addConstraint(lambda a, b: len(a) > 0 and len(b) > 0 and a[0] == b[0], \"T(1) T(2)\".split()) # T(1)[3] >= T(3)[1] rule problem.addConstraint(lambda a, b: len(a) > 2 and len(b) > 0 and a[2] >= b[0], \"T(1) T(3)\".split()) # implicit AND short_names = dict((val, \"T%d\" % i) for i, val in enumerate(possible_values, 1)) for solution in problem.getSolutionIter(): print \", \".join(\"%s: %s\" % (variable, short_names[value]) for variable, value in sorted(solution.iteritems()))您可以将规则合并为单个约束：# T(1)[1] = T(2)[1] AND T(1)[3] >= T(3)[1] problem.addConstraint(lambda a, b, c: (len(a) > 2 and b and c and a[0] == b[0] and a[2] >= c[0]), variables)