정수 입력 배열이 규칙 세트와 "일치"하는지 여부를 결정하고 싶습니다.복잡한 필터 규칙을 유사한 형식으로 줄임
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
규칙을 만족합니다.
문제는
는 여전히 규칙을 설명하는 가장 간단하고 기본적인 형태에 매처 (matcher)를 줄일 필요가있다. 예를 들면, 상기 정합 주어진 샘플 감소 될 수있다 :
rules = {
or: [1, 2],
xor: [], // No XORs
nor: [4]
}
각 정수 rule
rule
또는 S로 구성된 서브 규칙의 세 가지 배열을 갖는다.
1
이 반드시 필요하기 때문에 OR이 비어 있습니다. 이는 만족해야하므로 OR(0, 1) => [0, 1]
이 중복됨을 의미합니다. 이제
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))
, 많은 양의 :
Matcher
이후의 (나는 기본 규칙 사이의 동등성을 판단 할 수 있어야합니다) 내가에 도착하면, 그것은 조금 더 복잡하게 비교해야 그것의 중복 및/또는 모순, 그래서 내가 할 수있는 생각은 처음으로 그것을 나무 같은 구조로 배치하고, 다음 그것을 재발행하고 불필요한 항목을 줄일 수 있습니다. 이 작업을 수행하는 더 좋은 방법에 대한 아이디어가 있습니까?
저는 특히 결정론적인 것을 말합니다 (동일한 최종 축소 형을 산출하는 입력 규칙의 집합). 이 문제를 표현하는 더 좋은 방법이 있다면, 저는 관심이 있습니다. 규칙이 모순되면 예외를 파기하고 감속시키는 것이 좋습니다. 이는 프로그램에서 가끔씩 사용하기위한 것이므로 성능에 별 문제가되지 않습니다.
그래서 이것은 NP 완성이고 해결할 가능성이없는 만족할만한 문제의 사례 일 수 있다고 알려졌습니다. – AniSkywalker