Re: how to count inversions? - homework

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
.