I'm attempting to find the amount of inversions within a list. Inversions would be defined as any pair a,b from a list, where ai is the index of a and bi is the index of b that satisfies a > b and ai < bi. Essentially a comes before b but yet is larger than b.
The first thing I did was write a predicate to find out what the index is.
indexOf(Index, Element, List) :-
nth1(Index, List, Element).
Then I wrote a predicate to determine if any set of two numbers is an inversion
isInversion(A, B, List) :-
A \= B, indexOf(AI, A, List), indexOf(BI, B, List), A > B, AI < BI.
At this point I have a lot of questions, especially as I'm very unfamiliar with logic programming languages. My first question is, indexOf won't actually give me the index will it? I'm confused how that would actually work as it seems like it'd essentially have to try every number, which I'm not explicitly telling it to do.
If somehow indexOf will automatically determine the index and store it in AI/BI like I'm expecting, then I believe my isInversion predicate will evaluate correctly, if I'm wrong please let me know.
My main concern is how to actually determine the amount of inversions. In something like python I would do
count = 0
for a in puzzle
for b in puzzle
if a is b continue
if isInversion(a, b, puzzle)
count = count + 1
That would give me my amount of inversions. But how can I do this in prolog? For loops don't seem very stylistic so I don't want to use that.
Something to note, I have searched for other questions. It's a little tough since I obviously don't know exactly what I'm trying to look for. However I just wanted to make it clear that I felt things such as Prolog do predicate for all pairs in List? didn't help me answer the question.
You should remove the constraint A\=B as it will fail with unbound variables.
Then use aggregate_all/3 to count all the inversions (you don't actually need the values A/B of the 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).
Sample run:
?- countInversions([4,3,2,1,9], N).
N = 6.
You may see which inversions exists using findall/3 on 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].