Я хочу определить, соответствует ли входной массив целых чисел «набору правил».Сокращение сложных правил фильтрации в сопоставимой форме
сличитель
Matcher построен из набора вспомогательных методов для описания правил для ввода данных. Эти правила в основном логические элементы массивов целых чисел:
AND(1, 2) // Requires both 1 AND 2 be present in the input array.
OR(3, 4, 5) // Requires that 3 OR 4 OR 5 be present in the input array.
NOR(6, 7) // Requires that neither 6 NOR 7 be present in the input array.
XOR(8, 9) // Requires that either 8 (X)OR 9 be present in the input array, but not both.
Таким образом, я мог бы сказать, что, учитывая входной массив:
[0, 1, 2, 3]
Я мог бы построить Matcher как:
AND(OR(0, 1), AND(1, 2) NOR(4))
Который соответствовал бы входному сигналу, поскольку вход удовлетворяет:
OR(0, 1) // 0 or 1 is present
AND(1, 2) // Both 1 and 2 are present
NOR(4) // 4 is not present
И каждый из них в совокупности удовлетворяет общему правилу AND.
Проблема
мне нужно уменьшить matchers к наиболее простой и основной форме, которая до сих пор описывает правила. Например, с учетом приведенной выше согласованью, сокращение образца может быть:
rules = {
or: [1, 2],
xor: [], // No XORs
nor: [4]
}
Каждого rule имеет три массивов подправил, состоящие из целых или rule с.
Обратите внимание, что ORs пустые, так как в любом случае требуется 1, что означает, что OR(0, 1) => [0, 1] является излишним, потому что он должен быть удовлетворен.
С Matcher лет должны быть сопоставимы (я должен быть в состоянии определить эквивалентность между лежащими в основе правил), становится немного более сложным, когда я получаю:
input = [1, 2, 5, 9, 11, 12, 13, 14, 17]
XOR(OR(AND(1, 2), NOR(3, 4), XOR(3 11), AND(11, 14)), AND(1, 5, 17))
В настоящее время, большое количество из этого является избыточным и/или противоречивым, поэтому то, что я думал, что я мог сделать, было сначала помещать его в древовидную структуру, а затем рекурсировать и уменьшить ненужные записи. Любые идеи для лучшего способа сделать это?
Я специально искал что-то детерминированное (любой набор правил ввода, который означает одно и то же, дает ту же конечную уменьшенную форму). Если есть лучший способ выразить эту проблему, мне интересно, и если правила противоречивы, это нормально для редуктора, чтобы сломать и выбросить исключение. Это предназначено для случайного использования в программе, поэтому производительность не является большой проблемой.
Поэтому мне сообщили, что это может быть пример проблемы выполнимости, который является NP-полным и, следовательно, вряд ли разрешимым. – AniSkywalker