如何在Prolog中找到列表中的反转数 [英] How to find the number of inversions in a list in Prolog

问题描述

作为Prolog的新手，我正在寻找一种计算列表中反转次数的好方法.

As someone who's new to Prolog, I'm looking to find out what a good way to count the number of inversions in a list.

我知道如何使用flatten(Matrix, FlatMatrix)展平矩阵，从而创建一个在矩阵中包含一组元素的变量.但是，我不确定如何找到该列表中的反转数.

I know how to flatten a matrix using flatten(Matrix, FlatMatrix), thus creating a variable that contains a single set of elements in the matrix. However, I'm unsure as to how to go about finding the number of inversions in that list.

根据我的理解，从0 ... n的数字矩阵中的求逆数是小于要比较的元素的总数(如果我错了，请纠正我).

From my understanding, the number of inversions in a matrix of numbers from 0...n is the total number of elements that are less than the number being compared (please correct me if I'm wrong on this).

我对setof/3在Prolog中的工作原理了解得很少，但是我很想知道一种更有效的方法来解决扁平矩阵中的求逆数. Prolog中的变量对我来说很奇怪，因此最好是简单的解释.

I have a tiny bit of understanding of how setof/3 works in Prolog but I'd love to know a more efficient way to tackle the figuring out of the number of inversions in a flattened matrix. Variables in Prolog are strange to me so simple explanations would be best.

提前谢谢！

推荐答案

首先，我不太了解您所说的反演"的含义，因此我将坚持准规范的解释，即 @CapelliC在此问题的答案中使用了 .

First, I didn't quite get the meaning of what you were calling "inversion", so I'll stick to the quasi-canonical interpretation that @CapelliC used in his answer to this question.

让我们假设所有列表项都是整数，因此我们可以使用 clpfd .

Let's assume that all list items are integers, so we can use clpfd.

:- use_module(library(clpfd)).

z_z_order(X,Y,Op) :-
   zcompare(Op,X,Y).

要计算反转次数(上下方向变化)，我们执行以下四个步骤:

To count the number of inversions (up-down direction changes), we do the following four steps:

1. 比较相邻项(使用mapadj/3，如本答案结尾处所定义)

1. compare adjacent items (using mapadj/3, as defined at the very end of this answer)

?- Zs = [1,2,4,3,2,3,3,4,5,6,7,6,6,6,5,8], mapadj(z_z_order,Zs,Cs0).
Zs  = [1,2,4,3,2,3,3,4,5,6,7,6,6,6,5,8],
Cs0 = [ <,<,>,>,<,=,<,<,<,<,>,=,=,>,< ].

消除Cs0中所有出现的=(使用 tfilter/3 和 )

eliminate all occurrences of = in Cs0 (using tfilter/3 and dif/3)

?- Cs0 = [<,<,>,>,<,=,<,<,<,<,>,=,=,>,<,<], tfilter(dif(=),Cs0,Cs1).
Cs0 = [<,<,>,>,<,=,<,<,<,<,>,=,=,>,<,<],
Cs1 = [<,<,>,>,<,  <,<,<,<,>,    >,<,<].

在Cs1中获得相等项的运行(使用 splitlistIfAdj/3 和 )

get runs of equal items in Cs1 (using splitlistIfAdj/3 and dif/3)

?- Cs1 = [<,<,>,>,<,<,<,<,<,>,>,<,<], splitlistIfAdj(dif,Cs1,Cs).
Cs1 = [ <,< , >,> , <,<,<,<,< , >,> , <,< ],
Cs  = [[<,<],[>,>],[<,<,<,<,<],[>,>],[<,<]].

反转次数比运行次数少1(使用 length/2 和

the number of inversions is one less than the number of runs (using length/2 and (#=)/2)

?- Cs = [[<,<],[>,>],[<,<,<,<,<],[>,>],[<,<]], length(Cs,L), N #= max(0,L-1).
Cs = [[<,<],[>,>],[<,<,<,<,<],[>,>],[<,<]], L = 5, N = 4.

就是这样.让我们把它们放在一起！

That's it. Let's put it all together!

zs_invcount(Zs,N) :-
   mapadj(z_z_order,Zs,Cs0),
   tfilter(dif(=),Cs0,Cs1),
   splitlistIfAdj(dif,Cs1,Cs),
   length(Cs,L),
   N #= max(0,L-1).

样品用途:

?- zs_invcount([1,2,3],0),    
   zs_invcount([1,2,3,2],1),    
   zs_invcount([1,2,3,3,2],1),               % works with duplicate items, too
   zs_invcount([1,2,3,3,2,1,1,1],1),
   zs_invcount([1,2,3,3,2,1,1,1,4,6],2),
   zs_invcount([1,2,3,3,2,1,1,1,4,6,9,1],3),
   zs_invcount([1,2,3,3,2,1,1,1,4,6,9,1,1],3).
true.

---

meta-predicate的实现 mapadj/3

---

Implementation of meta-predicate mapadj/3

:- meta_predicate mapadj(3,?,?), list_prev_mapadj_list(?,?,3,?).
mapadj(P_3,[A|As],Bs) :-
   list_prev_mapadj_list(As,A,P_3,Bs).

list_prev_mapadj_list([]     ,_ , _ ,[]).
list_prev_mapadj_list([A1|As],A0,P_3,[B|Bs]) :-
   call(P_3,A0,A1,B),
   list_prev_mapadj_list(As,A1,P_3,Bs).

这篇关于如何在Prolog中找到列表中的反转数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！