Programma Prolog per trovare l'uguaglianza di due elenchi in qualsiasi ordine

Question

Volevo scrivere un programma Prolog per trovare l'uguaglianza di due elenchi, in cui l'ordine degli elementi
non ha importanza. Così ho scritto il seguente:

del(_, [], []) . 
del(X, [X|T], T). 
del(X, [H|T], [H|T1]) :- 
    X \= H, 
    del(X, T, T1). 

member(X, [X|_]). 
member(X, [_|T]) :- 
    member(X, T). 

equal([], []). 
equal([X], [X]). 
equal([H1|T], L2) :- 
    member(H1, L2), 
    del(H1, L2, L3), 
    equal(T, L3). 

Ma quando do ingresso come equal([1,2,3],X)., esso non mostra tutti i possibili valori di X. Invece, il programma si blocca nel mezzo. Quale potrebbe essere la ragione?

Answer 1

isSubset([],_). 
isSubset([H|T],Y):- 
    member(H,Y), 
    select(H,Y,Z), 
    isSubset(T,Z). 
equal(X,Y):- 
    isSubset(X,Y), 
    isSubset(Y,X). 

Answer 2

Prova questo:

equal([],[]). 
equal([Ha|Ta],[Hb|Tb]) :- 
    Ha = Hb, lequal(Ta,Tb). 

Answer 3

Provare a utilizzare predicato che controlla se uno dei set è una permutazione di altri set:

delete(X, [X|T], T). 

delete(X, [H|T], [H|S]):- 
    delete(X, T, S). 


permutation([], []). 

permutation([H|T], R):- 
    permutation(T, X), delete(H, R, X). 

(predicato tratto da http://www.dreamincode.net/code/snippet3411.htm)

?- permutation([1,2,3],[3,1,2]). 
true 

Answer 4

Io suggerisco di usare il built-in p redicare msort/2, quindi confrontare gli elenchi. Prende O (nlogn) tempo su SWI Prolog, mentre il controllo di liste non ordinate in modo ingenuo elemento per elemento richiederebbe il tempo O (n).

lists_equal(List1, List2) :- 
    msort(List1, Sorted1), 
    msort(List2, Sorted2), 
    Sorted1=Sorted2. 

Qui, l'ordinamento elenchi prende O (nlogn) tempo, e il confronto prende O (n) su SWI Prolog, non so su altre implementazioni.

Answer 5

brevemente

equal([],[]). 
equal([H|T],[H|T1]):-equal(T,T1). 

Answer 6

ne dite:

equal(X, Y) :- 
    subtract(X, Y, []), 
    subtract(Y, X, []). 

Answer 7

Se non si preoccupano le molteplicità degli elementi della lista e si utilizza solo il predicato con instantiation sufficiente, in considerazione di fare in questo modo:

same_elements(As,Bs) :- 
    ( ground(As+Bs) 
    -> maplist(sort, [As,Bs], [Es,Es])  % same as `sort(As,Es), sort(Bs,Es)` 
    ; throw(error(instantiation_error,_)) 
    ). 

Answer 8

Il motivo reale della non-terminazione che si osserva ed è questo: la seguente clausola non vincola L2 in alcun modo, forma o forma.

 
equal([H1|T], L2) :- 
    member(H1, L2), 
    del(H1, L2, L3), 
    equal(T, L3). 

Quindi la query ?- equal([1,2,3], X). implica dimostrando l'obiettivo member(_, L2) che non pone fine universalmente. Pertanto, equal([1,2,3], X) non può terminare anche universalmente!

Per ulteriori informazioni su come spiegare la mancata terminazione del codice Prolog, leggere failure-slice!

---

PS. Osservando il problema di terminazione da una diversa angolazione, vediamo che la non-terminazione è, in effetti, una conseguenza necessaria in questo caso.

Perché? Perché non si limita il numero di moltiplicazioni, il che rende la soluzione impostata di dimensioni infinite. Il set non può essere rappresentato da un numero finito di risposte (a condizione che non si consentano di ritardare gli obiettivi).

Answer 9

Quindi perché equal([1,2,3], X) non termina universalmente con il codice?

Diamo un'occhiata a failure-slice del tuo codice! Quali sono le fette di fallimento? Ecco le informazioni tag:

A failure-slice is a fragment of a Prolog program obtained by adding some goals false . Failure-slices help to localize reasons for universal non-termination of a pure monotonic Prolog program. They also help to give a lower bound for the number of inferences needed. It is a concrete program-slicing technique.

Per creare una fetta fallimento:

• inseriamo false obiettivi nel programma
• mentre assicurandosi che il frammento non termina con l'obiettivo di cui sopra.

 
del(_, [], []) :- false. 
del(X, [X|T], T) :- false. 
del(X, [H|T], [H|T1]) :- false, 
    dif(X, H),     % note that the OP originally used `X \= H` 
    del(X, T, T1). 

member(X, [X|_]). 
member(X, [_|T]) :- 
    member(X, T). 

equal([], []) :- false. 
equal([X], [X]) :- false. 
equal([H1|T], L2) :- 
    member(H1, L2), false, 
    del(H1, L2, L3), 
    equal(T, L3). 

?- equal([1,2,3], _), false.  % note that `false` is redundant ... 
** LOOPS **      % ... as above `equal/2` cannot succeed. 

Quindi ... cosa fa sopra fetta fallimento dirci? Dice:

• per rendere l'obiettivo equal([1,2,3], X) terminare universalmente ...
• ... noi dobbiamo cambiare di almeno una delle parti restanti (quelli non striked-through)!