时间戳

首页 > 解决方案 > 查找列表中出现的谓词

prolog - 查找列表中出现的谓词

问题描述

我正在尝试查找列表中的反转数量。反转将被定义为a,b列表中的任何对，其中ai是 的索引a和bi是b满足a > b和的索引ai < bi。本质上 a 在 b 之前，但大于 b。

我做的第一件事是写一个谓词来找出索引是什么。

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

然后我写了一个谓词来确定任何两个数字的集合是否是反转

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

在这一点上，我有很多问题，特别是因为我对逻辑编程语言非常不熟悉。我的第一个问题是，indexOf 实际上不会给我索引吗？我很困惑这实际上是如何工作的，因为它似乎基本上必须尝试每个数字，我没有明确告诉它这样做。

如果 indexOf 会像我期望的那样自动确定索引并将其存储在 AI/BI 中，那么我相信我的 isInversion 谓词会正确评估，如果我错了，请告诉我。

我主要关心的是如何实际确定反转的数量。在类似 python 的东西中，我会做

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

那会给我我的倒数。但是我怎么能在序言中做到这一点？For 循环看起来不是很有风格，所以我不想使用它。

需要注意的是，我已经搜索了其他问题。这有点困难，因为我显然不知道我要寻找什么。但是我只是想明确一点，我觉得诸如Prolog 之类的东西对 List 中的所有对都做了谓词？没有帮助我回答这个问题。

标签： prolog

解决方案

您应该删除约束A\=B，因为它会因未绑定的变量而失败。

然后用于aggregate_all/3计算所有反转（实际上不需要反转的值 A/B）：

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

样品运行：

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

您可以使用findall/3on 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].

推荐阅读