적절한 하위 집합 - 프롤로그

Question

두 개의 목록을 입력으로 사용하고 적절한 하위 집합을 검사하는 프로그램을 작성하려고합니다. 나는 다음과 같이 시작했다 :

proper([A],[]). 
proper([],[A]). 
proper([A|T1],[A|T2]) :- proper(T1,T2). 

정확하게 똑같은 순서로 입력에 대해 완벽하게 작동한다. 예를 들면 :

Subset function in prolog

나를 인도 :

?- proper([a,b,c],[b,d,a,c]). 
No 

사이트를 통해보고 후 나는이 이전에 질문 질문을 발견 :

?- proper([a,b,c],[a,b,c,d]). 
Yes 

하지만 같은 입력에 대해 수행 내 코드를 다음과 같이 수정하십시오 :

proper([A],[]). 
proper([],[A]). 
proper([A|T1],[A|T2) :- member(A,T2), proper(T1,T2). 
proper([H1|T1], [H2|T2]) :- \+ member(H1, T2). 

하위 집합에는 적합하지만 하위 집합에는 적합하지 않습니다. 내 문제는 적절한/4의 두 번째 조항이 어떻게 작동하는지 이해함에 따라 발생한다고 생각합니다. 모든 도움이 크게 감사드립니다.

편집 :

내가 첫 번째 목록이 두 번째 및 두 번째의 부분 집합은 최초의 부분 집합이었다 여부를 결정하려고했다 깨달았다. 더 정확한 코드를 정리했습니다.

proper([],_). 
proper([A|T1],[A|T2) :- member(A,T2), proper(T1,T2). 
proper([H1|T1], [H2|T2]) :- \+ member(H1, T2). 

Answer 1

만약 내가 제대로 이해하고, 마지막 시도에서 처음 두 선언은 그 의미, 1 개 요소 목록 (false)를 빈리스트의 부분 집합 모두, 및 빈 list는 하나의 요소가있는 목록의 적절한 하위 집합입니다 (true). 첫 번째 것은 proper([1], [])뿐만 아니라 proper([],[1])이 성공할 것이기 때문에 문제가 될 수 있지만 적절한 부분 집합 관계는 비대칭입니다.

나는 두 번째 시도가 동일한 하위 집합을 필터링하지 않는 이유는 당신이

B.

보다 여기에 내가 생각 해낸 몇 가지 가능한 솔루션은 더 작은 될 수있는이 필요없는 선언이 없다고 믿습니다. 나는 명확함과 concision을 위해 smaller_set/2 몇 번을 사용한다.

smaller_set(A, B) :- 
    length(A, LA), 
    length(B, LB), 
    LA < LB. 

def_proper_subset/2

는 부분 집합의 표준 정의를 포착하려고합니다.

def_proper_subset(A, B) :- 
    smaller_set(A, B),     % if A < B then there's some _e in B that isn't in A. 
    forall(member(_e, A), member(_e, B)). 

그것은 보장 각 정합 A의 요소 B.를 removeing에 기초하여 재귀 적 정의와 예에만 후속 의해 < B는이

rec_proper_subset1([], [_|_]). 
rec_proper_subset1([_e|A], B) :- 
    select(_e, B, C),   % C is B with _e removed. Only true if _e is in B. 
    rec_proper_subset1(A, C). 

이것 B.

전에 요소 떨어지면 것을 주요 술어가 이미 A < B.을 보장하면 보조 관찰 술어를 사용하여 회원을 확인합니다.

rec_proper_subset2(A, B) :- 
    smaller_set(A, B), 
    rec_proper_subset2_(A, B). 

rec_proper_subset2_([], _). 
rec_proper_subset2_([_e|A], B) :- 
    member(_e, B), 
    rec_proper_subset2_(A, B). 

편집 :

• 당신은 당신이 당신의 목록을 중복 요소가없는 있는지 확인하려는 경우 유사한 list_to_set/2, sort/2, 또는 무언가를 사용해야합니다. 그러나 이러한 종류의 솔루션은 하위 목록을 찾는 데에도 도움이됩니다.
• def_proper_subset/2은 A가 B의 하위 집합이지만 A의 B 하위 집합을 생성 할 수 없는지 확인하기 위해 일종의 진절머리 난 솔루션이라고 생각합니다. 다른 두 개는 생각할 수 있습니다.

(내가 실수하여 rec_proper_subset2/2에 대한 기본 정의를 포함하는 것을 잊어 버렸지 만 지금 수정했습니다).