Быстрое сопоставление кортежей на основе условия

Я ищу быстрый алгоритм для следующей проблемы.

Правило представлено конъюнкцией предложений о кортежах. Предложение определяет отношение между двумя элементами кортежа. Например, T(1)[2] = T(3)[1] означает: the second item in the first tuple must be equal to the first one in the third.

Таким образом, правило может быть таким: 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

По сути, он будет определять, какие кортежи могут заменить каждый T (i), чтобы это правило было истинным.

Есть ли известный алгоритм для быстрого выполнения этого? Какие-либо предложения?

Спасибо,

A


match algorithm
person Andrew    schedule 17.04.2011    source источник
comment
правило T(1)[3]>T(3)[1] должно быть T(1)[3]>=T(3)[1] иначе решения нет.   -  person jfs    schedule 18.04.2011
comment
Ради Дейкстры используйте индексацию с отсчетом от нуля. на нуле   -  person jfs    schedule 18.04.2011

Ответы (3)


arrow_upward
0
arrow_downward

Поскольку вам нужно перечислить все возможные назначения, а не подсчитывать их количество, например, что может быть проще (хотя я так не думаю), единственный способ, вероятно, реализовать < href="http://en.wikipedia.org/wiki/Backtracking" rel="nofollow noreferrer">решение для поиска с возвратом.

EDIT: В частности, поскольку существует N! перестановок (где N — количество кортежей) исходного списка, которые могут удовлетворять ограничениям (в худшем случае), и вам нужно перечислить их, верхний граница O(N!) плотная.

person abeln    schedule 17.04.2011

arrow_upward
0
arrow_downward

Я думаю, что вы ищете что-то похожее на сеть Beta в алгоритме Rete http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.83.4551&rep=rep1&type=pdf

person Victor Hurdugaci    schedule 18.04.2011

arrow_upward
0
arrow_downward

Вы можете реализовать его как оболочку для модуля constraint. Вот решение для примера из вашего вопроса:

#!/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): T4, T(2): T1, T(3): T2
T(1): T1, T(2): T4, T(3): T2

Вы можете объединить правила в одно ограничение:

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

Чтобы установить модуль constraint, введите:

$ pip install http://labix.org/download/python-constraint/python-constraint-1.1.tar.bz2

person jfs    schedule 17.04.2011
comment
Вот вариант, который генерирует ограничения из правила, такого как T(1)[1] = T(2)[1] AND T(1)[3] >= T(3)[1], автоматически gist.github.com/35a2fac1255f23f57dea - person jfs; 18.04.2011