9
votes

Programme Prolog pour trouver l'égalité de deux listes dans n'importe quel ordre

Je voulais écrire un programme de prologs pour trouver l'égalité de deux listes, où l'ordre des éléments
Peu importe. Donc j'ai écrit ce qui suit: xxx

mais lorsque je donne une entrée comme égale ([1,2,3], x). , il ne montre pas tout Valeurs possibles de x . Au lieu de cela, le programme est suspendu au milieu. Quelle pourrait être la raison?


1 commentaires

C'est-à-dire de déterminer l'égalité de deux ensembles


9 Réponses :


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

1 commentaires

Le membre / 2 avant que le SELECT / 3 n'est pas nécessaire. L'égal / 2 ne fonctionne pas correctement: il ne donne qu'une solution puis sur Redo il est suspendu :? - égal ([1,2,3], x). X = [1, 2, 3]; Erreur: Exécution abandonnée depuis la mémoire faible. Donc voter la réponse.



1
votes

Essayez ceci:

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


0 commentaires

4
votes

Essayez d'utiliser le prédicat qui vérifie si l'un des ensembles est une permutation d'un autre ensemble: xxx

(prédicat tiré de http://www.dreamincode.net/code/snippet3411.htm ) xxx


1 commentaires

Le lien est mort.



0
votes

Je suggère d'utiliser le prédicat intégré msort / 2 code>, puis comparer les listes. Il prend une heure (Nlogn) sur Swi Prolog, alors que la vérification des listes non achonnes naïvement élément-élément prendrait O (N 2 sup>).

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


0 commentaires

-1
votes

brièvement xxx


1 commentaires

Cela ne fonctionnera pas si les listes contiennent les mêmes éléments dans un ordre différent.



1
votes

Que diriez-vous:

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


0 commentaires

2
votes

Si vous vous souciez de multiplicités des éléments de liste, Vérifiez une instanciation suffisante avec Sol / 1 , appliquer avec iquelg / 2 , et éliminer les duplicats avec Trier / 2 Comme: xxx

échantillon Utilisez avec swi prolog 8.0.0: xxx


0 commentaires

3
votes

La raison actuelle de la non-résiliation que vous avez observée est la suivante: la clause suivante ne contrainte pas l2 code> de quelque manière que ce soit, forme ou formulaire.

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


0 commentaires

1
votes

alors pourquoi égal ([1,2,3], x) code> ne se termine pas universellement avec votre code?

Regardons un de votre code! Quelles sont les tranches d'échec? Voici l'info TAG: P>

Une tranche d'échec est un fragment d'un programme de prologue obtenu en ajoutant certains objectifs false code>. Les tranches d'échec aident à localiser des raisons de non-résiliation universelle d'un programme PURE monotone-Prolog. Ils aident également à donner une limite inférieure au nombre d'inférences nécessaires. C'est une béton technique. p> blockQuote>

Pour créer une tranche d'échec: p>

  • Nous insérons faux b> code> objectifs dans le programme LI>
  • Tout en veillant à ce que le fragment ne se termine pas avec le but ci-dessus. LI> ul>
    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.
    
    • Pour faire le but égal ([1,2,3], x) code> Terminer universellement ... LI>
    • ... nous doit changer strong> au moins une des parties restantes fortes> (celles qui ne sont pas frappées s>)! LI> ul> p>


0 commentaires