Prolog - how to count inversions?

Author

how to count inversions? - homework

hapcimano@gmail.com

2007-04-24, 7:04 pm

Dear Community!

I've got a problem to solve for my University.

I have to count the inversions in a given list, and give this number
back as a solution.

The rule of inversion:
There is an array A[1...n], which got n different elements. If i<j,
and A[i]>A[j] then (i, j) is an inversion. (i, j) and (j, i) counts
only one.

An example:
query([10,30,20,40], N) -> N=1 because A[2]=30 > A[3]=20 while 2<3

query([2,3,8,6,1], N) -> N=5 because the inversions are (1,5); (2,5);
(3,5); (4,5); (3,4)

I've got a little help, I need to use insertion sort. Maybe I should
count the "insert" predict in the following code, but i'm not able to
implement this :(

Any help appreciated!!

Thank you:
hapcimano

insert_sort(List,Sorted):- i_sort(List,[],Sorted).
i_sort([],Acc,Acc).
i_sort([H|T],Acc,Sorted):-insert(H,Acc,NAcc), i_sort(T,NAcc,Sorted).

insert(X,[Y|T],[Y|NT]):- X>Y, insert(X,T,NT).
insert(X,[Y|T],[X,Y|T]):- X=<Y.
insert(X,[],[X]).

bart demoen

2007-04-24, 7:04 pm

On Tue, 24 Apr 2007 12:21:28 -0700, hapcimano wrote:

> An example:
> query([10,30,20,40], N) -> N=1 because A[2]=30 > A[3]=20 while 2<3
>
> query([2,3,8,6,1], N) -> N=5 because the inversions are (1,5); (2,5);
> (3,5); (4,5); (3,4)
>
> I've got a little help, I need to use insertion sort. Maybe I should
> count the "insert" predict in the following code, but i'm not able to
> implement this :(

If it is only "maybe", you shouldn't even think about starting to do it :-)
Do you really "need" to use insertion sort ? Maybe your teacher was over
enthousiastic and just meant that insertion sort could be an inspiration.
Anyway ...

Advice from an old carpenter: NEVER, NEVER, NEVER name a predicate query.

Here is a sketch of the fish you want to catch:

the number of inversions in an empty list is .... zero !
the number of inversions in a list L which starts with X and has tail T
is
the number of inversion in T
plus
the number of times X is bigger than a number in T

Done ?
You might see the similarity with insertion sort afterwards :-)

If someone should point out that this leads to non-tail recursive
preds and that you need accumulators, don't be distracted until the above
has turned into a working Prolog program. Please post it so that your
fellow students see your fish.

Cheers

Bart Demoen

Duncan Patton

2007-04-24, 10:03 pm

On Tue, 24 Apr 2007 21:40:47 +0200
bart demoen <bmd@cs.kuleuven.be> wrote:

>
> Advice from an old carpenter: NEVER, NEVER, NEVER name a predicate query.
>

Or a variable Var, for that matter ;-)

Dhu

Sponsored Links