Corretto sottoinsieme - Prolog

Question

Sto tentando di scrivere un programma che richiede due elenchi come input e controlla il sottoinsieme appropriato. Ho iniziato con:

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

Ciò funziona perfettamente per gli input nello stesso ordine. per esempio:

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

ma non per gli ingressi quali:

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

Dopo aver guardato attraverso il sito ho trovato questa domanda posta in precedenza:

Subset function in prolog

Che mi portano per modificare il mio codice in quanto tale:

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

Funziona bene per sottoinsiemi ma non per sottoinsiemi appropriati. Credo che il mio problema derivi dalla mia comprensione di come funziona la seconda clausola di/4 appropriato. Qualsiasi aiuto è molto apprezzato.

Edit:

sono reso conto che stavo cercando di determinare se il primo elenco è stato un sottoinsieme proprio del secondo e il secondo è stato un sottoinsieme proprio del primo. Pulito il codice per essere più preciso.

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

Answer 1

Se ho capito bene, le prime due dichiarazioni nel vostro ultimo tentativo significherebbe che, sia una lista con 1 elemento è un sottoinsieme proprio di una lista vuota (false), e che un vuoto lista è un sottoinsieme appropriato di una lista con un elemento (true); il primo dovrebbe essere problematico, perché proper([1], []) riuscirà così come proper([],[1]), ma la relazione di sottoinsieme corretta è asimmetrica.

Credo che la ragione che il secondo tentativo non filtra sottoinsiemi identici è che avete nessuna dichiarazione che richiede una di essere più piccolo di B.

Ecco alcune possibili soluzioni mi si avvicinò con. Io uso smaller_set/2 un paio di volte per maggiore chiarezza e concisione.

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

def_proper_subset/2 tenta di acquisire la definizione standard di un sottoinsieme.

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

Un esempio di definizione ricorsiva, basato su removeing ​​ciascun elemento corrispondente di A e B. Si assicura che A < B soltanto riuscire se A esaurisce elementi prima 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). 

Questo uno usa un predicato ausiliare per controllare l'appartenenza una volta che il predicato principale ha già assicurato che 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). 

Edit:

• Avrete bisogno di usare list_to_set/2, sort/2, o qualcosa di simile, se si vuole essere sicuri che le vostre liste non hanno gli elementi duplicati. Ma questo tipo di soluzioni funzionerà anche per trovare sotto-liste.
• Penso che def_proper_subset/2 sia una specie di soluzione scadente, perché funzionerà solo per verificare che A sia un sottoinsieme di B ma non possa generare un sottoinsieme di B in A. Gli altri due sono in grado di pensare.

(Ho sbagliato e ho dimenticato di includere la definizione di terra per rec_proper_subset2/2, ma ora l'ho riparato).