Recherche d'occurrences de prédicat dans la liste

Nov 19 2020

J'essaie de trouver la quantité d'inversions dans une liste. Les inversions seraient définies comme n'importe quelle paire a,bd'une liste, où aiest l'index de aet biest l'index de ce bqui satisfait a > bet ai < bi. Essentiellement, a précède b, mais il est plus grand que b.

La première chose que j'ai faite a été d'écrire un prédicat pour découvrir ce qu'est l'index.

indexOf(Index, Element, List) :- 
    nth1(Index, List, Element).

Ensuite, j'ai écrit un prédicat pour déterminer si un ensemble de deux nombres est une inversion

isInversion(A, B, List) :-
    A \= B, indexOf(AI, A, List), indexOf(BI, B, List), A > B, AI < BI.

À ce stade, j'ai beaucoup de questions, d'autant plus que je ne suis pas familier avec les langages de programmation logique. Ma première question est, indexOf ne me donnera pas réellement l'index, n'est-ce pas? Je ne sais pas comment cela fonctionnerait réellement, car il semble qu'il faudrait essentiellement essayer chaque numéro, ce que je ne lui dis pas explicitement de faire.

Si indexOf déterminera automatiquement l'index et le stockera dans AI / BI comme je m'y attendais, alors je pense que mon prédicat isInversion évaluera correctement, si je me trompe, veuillez me le faire savoir.

Ma principale préoccupation est de savoir comment déterminer réellement le montant des inversions. Dans quelque chose comme python je ferais

count = 0
for a in puzzle
    for b in puzzle
        if a is b continue
        if isInversion(a, b, puzzle)
            count = count + 1

Cela me donnerait ma quantité d'inversions. Mais comment puis-je faire cela en prologue? Les boucles For ne semblent pas très stylistiques, donc je ne veux pas m'en servir.

Quelque chose à noter, j'ai recherché d'autres questions. C'est un peu difficile car je ne sais évidemment pas exactement ce que j'essaie de rechercher. Cependant, je voulais juste préciser que je pensais que des choses telles que Prolog font un prédicat pour toutes les paires de List? ne m'a pas aidé à répondre à la question.

Réponses

2 gusbro Nov 19 2020 at 11:13

Vous devez supprimer la contrainte A\=Bcar elle échouera avec des variables indépendantes.

Ensuite, utilisez aggregate_all/3pour compter toutes les inversions (vous n'avez pas réellement besoin des valeurs A / B de l'inversion):

isInversion(A, B, List):-
    indexOf(AI, A, List),
    indexOf(BI, B, List),
    A > B,
    AI < BI.

countInversions(List, N):-
  aggregate_all(count, isInversion(_, _, List), N).

Exemple d'exécution:

?- countInversions([4,3,2,1,9], N).
N = 6.

Vous pouvez voir quelles inversions existent en utilisant findall/3sur isInversion:

?- findall(A-B, isInversion(A,B,[4,3,2,1,9]), LInversions).
LInversions = [4-3, 4-2, 4-1, 3-2, 3-1, 2-1].